1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
| #include<bits/stdc++.h> using namespace std; #define ll long long const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const int N = 5e5 + 10; const ll mod = 1e9 + 7; int n, q; vector<int>G[N]; int fa[N], siz[N], dep[N], son[N], topf[N], dfn[N], clk; void dfs1(int u, int _fa) { siz[u] = 1; fa[u] = _fa; for (int v : G[u]) { if (v == _fa)continue; dep[v] = dep[u] + 1; dfs1(v, u); siz[u] += siz[v]; if (siz[v] > siz[son[u]])son[u] = v; } } void dfs2(int u, int topfa) { topf[u] = topfa; dfn[u] = ++clk; if (!son[u])return; dfs2(son[u], topfa); for (int v : G[u]) { if (!topf[v])dfs2(v, v); } } int LCA(int u, int v) { while (topf[u] ^ topf[v]) { dep[topf[u]] < dep[topf[v]] ? v = fa[topf[v]] : u = fa[topf[u]]; } return dep[u] < dep[v] ? u : v; } bool cmp(int x, int y) { return dfn[x] < dfn[y]; } int top, s[N]; struct E { int v, w; }; vector<E>g[N]; void build(int* h,int k) { sort(h + 1, h + k + 1, cmp); s[top = 1] = 1; g[1].clear(); for (int i = 1, l; i <= k; i++) { if (h[i] != 1) { l = LCA(h[i], s[top]); if (l != s[top]) { while (dfn[l] < dfn[s[top - 1]]) { g[s[top - 1]].push_back(E{ s[top],dep[s[top]] - dep[s[top - 1]] }); g[s[top]].push_back(E{ s[top - 1],dep[s[top]] - dep[s[top - 1]] }); top--; } if (dfn[l] > dfn[s[top - 1]]) { g[l].clear(); g[l].push_back(E{ s[top],dep[s[top]] - dep[l] }); g[s[top]].push_back(E{ l,dep[s[top]] - dep[l] }); s[top] = l; } else { g[l].push_back(E{ s[top],dep[s[top]] - dep[l] }); g[s[top]].push_back(E{ l,dep[s[top]] - dep[l] }); top--; } } g[h[i]].clear(); s[++top] = h[i]; } } for (int i = 1; i < top; i++) { g[s[i]].push_back(E{ s[i + 1],dep[s[i + 1]] - dep[s[i]] }); g[s[i + 1]].push_back(E{ s[i],dep[s[i + 1]] - dep[s[i]] }); } } int ddp[N]; void dfs3(int u, int _fa) { for (E& e : g[u]) { if (e.v == _fa)continue; ddp[e.v] = ddp[u] + e.w; dfs3(e.v, u); } } int a[N], k; int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs1(1, 0); dfs2(1, 1); scanf("%d", &q); while (q--) { scanf("%d", &k); for (int i = 1; i <= k; i++) { scanf("%d", &a[i]); } build(a, k); ddp[1] = 0; dfs3(1, 0); int t = 0; for (int i = 1; i <= k; i++) { if (ddp[t] <= ddp[a[i]])t = a[i]; } ddp[t] = 0; dfs3(t, 0); int mx = 0; for (int i = 1; i <= k; i++) { mx = max(mx, ddp[a[i]]); } printf("%d\n", (mx + 1) / 2); } return 0; }
|