BZOJ2870 最长道路

最初觉得挺麻烦的一道题没思路。有点像并查集直接搞但是不好维护直径。

然后发现树上到任意一点的最远点一定是直径的两个端点之一。于是直接把直径是哪俩点记下来就好了。然后按点权从大到小往树里插。

然后莫名其妙地抢到了第二快。这么老的题也是蛮欣慰的。大概是读入优化2333

#include <bits/stdc++.h>

using namespace std;

void setRand() {

FILE* pf = fopen(".rs", "r");

int hsv;

if (pf) {

fscanf(pf, "%d", &hsv);

fclose(pf);

}

srand(hsv);

printf("Seed = %d\n", hsv);

pf = fopen(".rs", "w");

fprintf(pf, "%d", (hsv << 1) | (rand() & 1));

fclose(pf);

}

#define readArg(a,b) { if (argc > a) sscanf(args[a], "%d", &b); }

void mklr(int m, char s) {

int l, r;

do

l = rand() % m + 1, r = rand() % m + 1;

while (l > r);

printf("%d %d%c", l, r, s);

}

int main(int argc, char* args[]) {

setRand();

int n = 10, m = 10, k = 10;

readArg(1, n);

readArg(2, m);

readArg(3, k);

freopen("in.txt", "w", stdout);

printf("%d\n", n);

for (int i = 1; i <= n; ++ i)

printf("%d ", rand() % k + 1);

putchar(10);

for (int i = 2; i <= n; ++ i)

printf("%d %d\n", i - rand() % min(i - 1, m) - 1, i);

/*for (int i = 1; i <= n; ++ i) {

mklr(m, 32);

mklr(m, 10);

}*/

}