题意
给出一颗有n个节点的树，我们想增加一条边在1到x之间，使得d(1,v)的和最小,d(u,v)代表从u到v经过的最少的边,n<=2*10^5。
分析
这个一看应该就是树形dp。
如果不连这一条边，这个树本身的d(1,v)的和是多少?显然是每个点的深度的和（根结点深度为0）。那么连一条边（1，v）后，哪些点的深度受到了影响呢？首先它和它所有的子孙结点深度一定让减小。另外我们观察发现，从根结点到v路径上的中间结点以下的点节点深度也会减小。发现了这个规律应该就很好写了，实现的方法也非常多。
我们定义f[i]是连边（1，i）的d(1,v）的和。那么怎么转移呢？
当前在结点u，如果fa[u]的f值已经知道，如何求u的f值？我们来看，从（1，fa[u]）变为（1，u），哪些点的d（1，v）发生了变化？根据上面的规律很容易找到，u结点本身及其所有的子孙结点的d(1,v)值都减少了1，而1到u路径上的中间结点以下到fa[u]这些结点的d（1，v）值是加了1的。根据这个规律很容易推出所有结点的d值。
对了，写出来后一直是wa，很费解，出数据也没问题，long long也开了，就是不对。后来发现，对于long long类型的ans我初始化的时候仍然用的2147483647，所以就错了。。改大一点就A掉了···
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 typedef long long LL; 8 const int maxn=200000+10; 9 const int INF=2147483647; 10 11 vector<int>G[maxn]; 12 LL child[maxn],dep[maxn],f[maxn]; 13 int T,n,a,b; 14 LL ans; 15 void dfs1(int u,int fa){ 16 for(int i=0;i<G[u].size();i++){ 17 int v=G[u][i]; 18 if(v!=fa){ 19 dep[v]=dep[u]+1; 20 dfs1(v,u); 21 child[u]+=child[v]; 22 } 23 } 24 return; 25 } 26 int dis[maxn]; 27 void dfs(int u,int fa){ 28 dis[dep[u]]=u; 29 if(fa!=-1&&fa!=1){ 30 f[u]=f[fa]+child[dis[dep[u]/2+1]]-2*child[u]; 31 } 32 if(fa==1) 33 f[u]=f[fa]; 34 for(int i=0;i<G[u].size();i++){ 35 int v=G[u][i]; 36 if(v!=fa){ 37 dfs(v,u); 38 } 39 } 40 return; 41 } 42 43 int main(){ 44 scanf("%d",&T); 45 for(int t=1;t<=T;t++){ 46 scanf("%d",&n); 47 for(int i=1;i<=n;i++)G[i].clear(); 48 for(int i=1;i<n;i++){ 49 scanf("%d%d",&a,&b); 50 G[a].push_back(b); 51 G[b].push_back(a); 52 } 53 for(int i=1;i<=n;i++)child[i]=1; 54 dep[1]=0; 55 dfs1(1,-1); 56 for(int i=2;i<=n;i++)f[i]=INF;; 57 f[1]=0; 58 for(int i=1;i<=n;i++)f[1]+=dep[i]; 59 //cout<<f[1]<<endl; 60 dfs(1,-1); 61 ans=1e14; 62 for(int i=1;i<=n;i++)ans=min(ans,f[i]); 63 printf("%lld ",ans); 64 /*for(int i=1;i<=n;i++){ 65 printf("%d %d ",i,f[i]); 66 }*/ 67 } 68 return 0; 69 }