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.
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。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++.
<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, a, 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 fa, 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, x, 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, 0); 63 ans[1] = f[1]; 64 c[0] = 1; 65
66 solve(1, 0, 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 }
