虛樹求直徑。

const int N = int(1e6) + 9, LV = 21; VI adj[N]; int dfn[N], lfn[N], dep[N]; int tt; int n,m,cnt,ind,top; int fa[N][LV]; bool cmp(int a,int b) { return dfn[a]<dfn[b]; } void dfs(int u) { dfn[u] = ++tt; ECH(it, adj[u]) { int v = *it; if (v == fa[u][0]) continue; fa[v][0] = u; for (int lv=0;fa[v][lv+1]=fa[fa[v][lv]][lv];++lv); dep[v] = dep[u] + 1; dfs(v); } lfn[u] = tt; } inline int move_up(int x, int t){ for (int lv=0;t;++lv,t>>=1) if (t&1) x = fa[x][lv]; return x; } inline int move_to(int x, int t){ return move_up(x, dep[x]-t); } inline int lca(int x, int y) { if (dep[x]>dep[y]) swap(x,y); y=move_to(y, dep[x]); if (x==y) return x; DWN(lv, LV, 0) if (fa[x][lv]!=fa[y][lv]) x = fa[x][lv], y = fa[y][lv]; return fa[x][0]; } inline int dist(int x, int y) { return dep[x] + dep[y] - 2*dep[lca(x,y)]; } namespace Virtual_Tree { VI adj[N]; int sta[N], top; bool bj[N]; int total; PII f[N], diameter; void dfs(int u) { f[u] = {0, bj[u] ? -u : 0}; for (auto v: adj[u]) { dfs(v); int w = dep[v] - dep[u]; f[v].fi += w; checkMax(diameter, {f[u].fi + f[v].fi, max(f[u].se, f[v].se)}); checkMax(f[u], f[v]); total += w; } checkMax(diameter, f[u]); } void gao() { VI T; DO(m) { int x; RD(x); bj[x] = 1; T.PB(x); } UNQ(T, cmp); DWN(i, SZ(T)-1, 0) { int z = lca(T[i], T[i+1]); T.PB(z); } UNQ(T, cmp); top = 0; REP(i, SZ(T)) { int u = T[i]; while (top && lfn[sta[top]] < dfn[u]) --top; if (top) adj[sta[top]].PB(u); sta[++top] = u; } total = 0; diameter = {-INF, 0}; dfs(T[0]); printf("%d\n", -diameter.se); printf("%d\n", 2*total-diameter.fi); } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n, m); DO(n-1) { int x, y; RD(x, y); adj[x].PB(y); adj[y].PB(x); } dfs(1); Virtual_Tree::gao(); }