Edge to the Root
Time Limit: 1 Second Memory Limit: 131072 KB
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.
Input
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++.
Output
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).
Sample Input
2
6
1 2
2 3
3 4
3 5
3 6
3
1 2
2 3
Sample Output
8
2
Hint
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.
【分析】给你一棵树，1节点为根。现在在除1号节点外任选一个节点与1节点连一条边，使得其他所有节点到一号节点的距离之和最小，求这个最小的距离之和。
首先咱想一个暴力的方法。直接枚举每一个节点U，使其与1号节点连边，那么U节点及其子树的距离都会被改变，改变值为dis[u]-1（dis[u]=dep[u]-1）.再从1节点到U节点引一条路径，路径上的点及其子树的距离也会被改变，如果该路径上一个节点V的距离改变，那么该节点的所有子树（不包括该路径上的V的儿子节点及其子树）都会被改变，而且改变的差值都是一样的。现在我们就来分析一下哪些点会被更新。记录每一个节点的深度，dep[1]=1.比如dep[u]=6,即1–>2–>3–>4–>5–>6,当加一条边1–>6，则5,6节点及他俩的子树都会被改变，注意这里的路径上的节点都可能有子树，而且受5号节点影响的子树不包括6号节点（前面已说明）。
我们从6节点向上找到最后一个距离会被改变的节点，发现是5节点。而如果在6节点后面再接上7节点呢？可以发现还是5节点，然后再在纸上画几个发现：设向上最后一个被修改的节点为x，则dep[x]=dep[u]/2+2.（U为当前枚举的节点）。再看上边这个例子。5,6节点及其子树将被改变，对于6节点及其子树，改变值为(dis[6]-1)*sz[6],5节点及其子树：(dis[5]-1)*(sz[5]-sz[6]),合并得到 总改变值为2*(sz[5]+sz[6])，推广后，对于当前枚举节点dis是奇数的，差值为（2*（sz[u]+sz[fa[u]]+sz[fa[fa[u]]]…+sz[x]））而且可以推出当前节点dis为偶数时（dep为奇数），改变值为（2*（sz[u]+sz[fa[u]]+sz[fa[fa[u]]]…+sz[x]）-sz[x]）.号公式出来了，现在问题是怎么找这个x节点。嘻嘻，很简单，倍增记录祖先就行了，然后还得记录子树大小前缀和。
#include <bits/stdc++.h>
#define inf 1000000000
#define met(a,b) memset(a,b,sizeof a)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pb push_back
#define mp make_pair
typedef long long ll;
using namespace std;
const int N = 2e5+;
const int M = 4e2+;
const ll mod = 1e9+;
int n,m,k;
ll ans,sz[N],sum[N],pre;
int fa[N][],dep[N];
vector<int>edg[N];
void dfs1(int u,int f){
sz[u]=;
fa[u][]=f;
dep[u]=dep[f]+;
for(int i=;i<;i++){
fa[u][i]=fa[fa[u][i-]][i-];
}
for(int i=;i<edg[u].size();i++){
int v=edg[u][i];
if(v==f)continue;
dfs1(v,u);
sz[u]+=sz[v];
}
pre+=dep[u]-;
}
void dfs2(int u,int f){
sum[u]=sum[f]+sz[u];
for(int i=;i<edg[u].size();i++){
int v=edg[u][i];
if(v==f)continue;
dfs2(v,u);
}
}
int main() {
int op,u,v,x,y;
scanf("%d",&op);
while(op--){
pre=;
met(fa,);
for(int i=;i<N;i++){
edg[i].clear();
sum[i]=;
}
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
edg[u].pb(v);
edg[v].pb(u);
}
dep[]=;
dfs1(,);
dfs2(,);
ans=pre;
for(int i=;i<=n;i++){
int d=dep[i];
int x=d/+;
if(d==||d==)continue;
u=i;
for(int j=;j>=;j--){
if(dep[fa[u][j]]<x)continue;
else if(dep[fa[u][j]]>x)u=fa[u][j];
else {
u=fa[u][j];
break;
}
}
if(d&){
v=fa[u][];
ll ret=*(sum[i]-sum[v])-sz[u];
ans=min(ans,pre-ret);
}
else {
v=fa[u][];
ll ret=*(sum[i]-sum[v]);
ans=min(ans,pre-ret);
}
}
printf("%lld\n",ans);
}
return ;
}
