给出一棵n个点的无根树，求出以哪个点为根时，所有点的深度和最大，若有多个答案，输出编号最小的点
水题，先以1为根，求出所有点的初始深度，然后对于以1个根的答案，就是初始深度和
求初始深度时，顺便记录每个点的子树大小
然后让1继续深搜，我们发现一旦新遍历到一个点y，就将答案-sum[y]+n-sum[y]就行了，这么水，随便yy
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; struct node { int x,y,next; }a[2100000];int len,last[1100000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int sum[1100000],dep[1100000]; void dfs(int x,int fa) { sum[x]=1; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y==fa) continue; dep[y]=dep[x]+1; dfs(y,x); sum[x]+=sum[y]; } } LL s[1100000];int n; void solve(int x,int fa) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y==fa) continue; s[y]=s[x]-sum[y]+n-sum[y]; solve(y,x); } } int main() { scanf("%d",&n); len=0;memset(last,0,sizeof(last)); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); ins(x,y);ins(y,x); } dep[1]=1;dfs(1,0); s[1]=0; for(int i=1;i<=n;i++) s[1]+=dep[i]; solve(1,0); LL mmax=0;int t; for(int i=1;i<=n;i++) if(mmax<s[i]){mmax=s[i],t=i;} printf("%d\n",t); return 0; }
原文：https://www.cnblogs.com/Never-mind/p/9723012.html