Given a tree with n vertices, we want to add an edge between vertex 1 and vertex x, so that the sum of d(1, v) for all vertices v in the tree is minimized, where d(u, v) is the minimum number of edges needed to pass from vertex u to vertex v. Do you know which vertex x we should choose?
Recall that a tree is an undirected connected graph with n vertices and n - 1 edges.
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 2 × 105), indicating the number of vertices in the tree.
Each of the following n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n), indicating that there is an edge between vertex u and v in the tree.
It is guaranteed that the given graph is a tree, and the sum of n over all test cases does not exceed 5 × 105. As the stack space of the online judge system is not very large, the maximum depth of the input tree is limited to about 3 × 104.
We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
For each test case, output a single integer indicating the minimum sum of d(1, v) for all vertices v in the tree (NOT the vertex x you choose).
For the first test case, if we choose x = 3, we will have
d(1, 1) + d(1, 2) + d(1, 3) + d(1, 4) + d(1, 5) + d(1, 6) = 0 + 1 + 1 + 2 + 2 + 2 = 8
It's easy to prove that this is the smallest sum we can achieve.
现场赛的时候应该是写出正解了...但是不知道为什么挂了
结果回来按照记忆默了一遍七分钟直接就1A了
--------------------------------------------------------------------------------
枚举每个点，他子树中所有节点都会经过他到根，他到根上中点这段路径上的所有节点和他们的子树也会经过他到根
那么考虑按照深度枚举每个转移点，假设现在是d,中点为x，下一个枚举位置为t,son[]表示子树中节点个数
显然当枚举点往下移的时候，t所有的子节点到根的路径都会从由d跳转变为由t跳转，这样整体会减一
然后不考虑x的下移，那么x到d这段路径上所有点和他们子树中的节点的路径都会加1
再考虑x是否下移，移动的话则将x不包括t的所有子树中的点直接走向根，这里的贡献和到d再到根是一致的，因此不需要变化。
最后通过回溯来消除变化，这样直接将所有点dfs一遍即可求出最小的答案
#include<cstdio> #include<string> #include<cstring> #include<algorithm> using namespace std; struct line { int s,t; int next; }a[400001]; int head[200001]; int edge; inline void add(int s,int t) { a[edge].next=head[s]; head[s]=edge; a[edge].s=s; a[edge].t=t; } int fa[200001],son[200001],dep[200001]; inline void dfs1(int d) { int i; for(i=head[d];i!=0;i=a[i].next) { int t=a[i].t; if(t!=fa[d]) { fa[t]=d; dep[t]=dep[d]+1; dfs1(t); son[d]+=son[t]+1; } } } long long sx,ans,sx1,sx2; int nxt[200001]; inline void dfs2(int d,int x) { // printf("d:%d x:%d sx:%lld sx1:%lld sx2:%lld\n",d,x,sx,sx1,sx2); int i; for(i=head[d];i!=0;i=a[i].next) { int t=a[i].t; if(t!=fa[d]) { long long lx=x,lsx=sx,lsx1=sx1,lsx2=sx2; if(dep[x]<dep[d]-dep[x]+2) { if(x!=d) { if(dep[x]<dep[d]-dep[x]+1) sx-=son[x]-son[nxt[x]]; sx2-=son[x]-son[nxt[x]]; x=nxt[x]; } else { x=t; sx2-=son[d]-son[t]; } } sx1-=son[d]-son[t]; sx2+=son[d]-son[t]; if(dep[t]>1) sx-=sx1; sx+=sx2; ans=min(ans,sx); nxt[d]=t; dfs2(t,x); x=lx; sx=lsx; sx1=lsx1; sx2=lsx2; } } } int main() { int T; scanf("%d",&T); while(T>0) { T--; int n; scanf("%d",&n); edge=0; memset(fa,0,sizeof(fa)); memset(son,0,sizeof(son)); memset(head,0,sizeof(head)); int i,s,t; for(i=1;i<=n-1;i++) { scanf("%d%d",&s,&t); edge++; add(s,t); edge++; add(t,s); } dep[1]=0; dfs1(1); ans=0; for(i=1;i<=n;i++) ans+=dep[i]; sx=ans; sx1=son[1]+1; sx2=0; dfs2(1,1); printf("%lld\n",ans); } return 0; }
