求树的直径
#include <stdio.h> #include <string.h> const int MAXN = 100010; struct node { int to, next; }data[MAXN*2]; int head[MAXN], n, m, sz; void add(int u, int v) { data[sz].to = v; data[sz].next = head[u]; head[u] = sz++; data[sz].to = u; data[sz].next = head[v]; head[v] = sz++; } int fnum[MAXN], snum[MAXN], cnt[MAXN]; void dfs(int u, int pre) { int v, i; fnum[u] = snum[u] = 0; for (i = head[u]; ~i; i=data[i].next) { if ( (v=data[i].to) == pre) continue; dfs(v, u); if (fnum[v]+1 > fnum[u]) { snum[u] = fnum[u]; fnum[u] = fnum[v]+1; } else if (fnum[v]+1 > snum[u]) { snum[u] = fnum[v]+1; } } i = head[u]; if (u != 1) if (i == -1 || data[i].next == -1) /// leaf node { fnum[u]=snum[u] = 0; cnt[u] = 0; return; } int c1=0, c2=0; for (i = head[u]; ~i; i=data[i].next) { if ( (v=data[i].to) == pre) continue; if (fnum[u] == fnum[v]+1) c1++; else if (snum[u] == fnum[v]+1) c2++; } if (c1 >= 2) { cnt[u] = fnum[u]*2; } else if (c1 >= 1 && c2 >= 1) { cnt[u] = fnum[u]+snum[u]; } else cnt[u] = fnum[u]; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif // ONLINE_JUDGE int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); sz = 0; memset(head, -1, sizeof head); for (int i = 1; i< n; i++) { int u, v; scanf("%d%d", &u, &v); add(u, v); } dfs(1, -1); int mx = 0; for (int i = 1; i<= n; ++i) { if (cnt[i] > mx) mx=cnt[i]; } ++mx; for (int i = 0; i< m; ++i) { scanf("%d", &sz); if (sz <= mx) printf("%d\n", sz-1); else printf("%d\n", mx-1+(sz-mx)*2); } } return 0; }