B - Edge to the Root （树上dfs+思维）

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 × 10⁵),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 × 10⁵. 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 × 10⁴.

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++.

<h4< dd="">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).

<h4< dd="">Sample Input

2 6 1 2 2 3 3 4 3 5 3 6 3 1 2 2 3 

<h4< dd="">Sample Output

8 2 

<h4< dd="">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.

这题有人把它分在了树形dp里，感觉并不像是dp，有点从上到下递推的意思，

开始知道是从上往下推，但是就是想不出来是怎么推了，这就很蒟了，

其实就是考虑我把这个边往下移能带来什么后果，

比如从f 转移到了f的儿子son

son整个子树所经过的距离全都少了1

然后f和root中点 到 f 间所有的点的距离都增加了1

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;  4 
 5 #define rep(i,a,b)    for (int i(a); i <= (b); ++i)
 6 #define dec(i,b)    for (int i(a); i >= (b); --i)
 7 
 8 typedef long long LL;  9 
10 const int N = 2e5 + 10; 11 
12 int T,n; 13 int sz[n],deep[n]; 14 int c[n]; 15 
16 LL f[n]; 17 LL ans[n],all,ret; 18 vector <int> v[n]; 19 
20 void dfs(int x,int fa,int dep){ 21     sz[x]   = 1; 22     f[x]    = 0; 23     deep[x] = dep; 24 
25     for (int i=0;i<v[x].size();i++) { 26         int u=v[x][i]; 27         if (u == fa) conTinue; 28         dfs(u,x,dep + 1); 29         sz[x] += sz[u]; 30         f[x]  += 0ll + f[u] + sz[u]; 31  } 32 } 33 
34 void solve(int x,int dep) 35 { 36       for (int i=0;i<v[x].size();i++) 37  { 38         int u=v[x][i]; 39         if (u == fa) conTinue; 40         c[dep] = u; 41         if (deep[u] >= 2) ans[u] = ans[x] + sz[c[dep / 2 + 1]] - 2 * sz[u]; 42         else ans[u] = ans[x]; 43         solve(u,dep + 1); 44  } 45 } 46         
47 
48 int main(){ 49 
50     scanf("%d",&T); 51 
52     while (T--){ 53         scanf("%d",&n); 54         rep(i,0,n + 1) v[i].clear(); 55         rep(i,2,n){ 56             int x,y; 57             scanf("%d%d",&x,&y); 58  v[x].push_BACk(y); 59  v[y].push_BACk(X); 60  } 61 
62         dfs(1,0); 63         ans[1] = f[1]; 64         c[0] = 1; 65 
66         solve(1,1); 67 
68         ret = ans[1]; 69 
70         rep(i,2,n) ret = min(ret,ans[i]); 71         printf("%lld\n",ret); 72  } 73 
74 
75     return 0; 76 }