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("%lldn",ret); 72  } 73 
74 
75     return 0; 76 }