题目大意：
给定一棵n个结点的树，求一个点x作为根，使得所有结点到x的距离和最小。思路：
树形DP。 首先考虑将1作为根的情况。 很显然我们可以用一遍O(n)的DFS预处理出每个结点所对应子树大小size和子树内每个结点到这个结点的距离和sum。 这样也就相当于我们递推求出了以1作为根时各结点到它的距离和。 现在考虑将根往下转移。 假设我们现在要从u转移到v，那么显然在sum[u]的基础上，sum[v]需要变化的是(u,v)之间的连接的边。 也就是说sum[y]=sum[x]+n-size[y]*2。 这样我们就可以用O(n)时间将根往下转移。 总的时间复杂度还是O(n)的。1 #include2 #include 3 typedef long long int64; 4 inline int getint() { 5 register char ch; 6 while(!isdigit(ch=getchar())); 7 register int x=ch^'0'; 8 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9 return x;10 }11 const int N=1000001;12 int head[N],to[N<<1],next[N<<1],sz;13 inline void add_edge(const int &u,const int &v) {14 to[++sz]=v; next[sz]=head[u]; head[u]=sz;15 to[++sz]=u; next[sz]=head[v]; head[v]=sz;16 }17 int64 sum[N],max;18 int n,size[N],root;19 void dfs(const int &x,const int &par) {20 size[x]=1;21 for(int i=head[x];i;i=next[i]) {22 const int &y=to[i];23 if(y==par) continue;24 dfs(y,x);25 size[x]+=size[y];26 sum[x]+=sum[y]+size[y];27 }28 }29 void move(const int &x,const int &par) {30 if(sum[x]>max) {31 max=sum[x];32 root=x;33 } else if(sum[x]==max&&x