题目描述
有一个村庄居住着 nn 个村民，有 n-1n−1 条路径使得这 nn 个村民的家联通，每条路径的长度都为 11。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。
输入格式
第一行，一个数 nn，表示有 nn 个村民。
接下来 n-1n−1 行，每行两个数字 aa 和 bb，表示村民 aa 的家和村民 bb 的家之间存在一条路径。
输出格式
一行输出两个数字 xx 和 yy。
xx 表示村长将会在哪个村民家中举办会议。
yy 表示距离之和的最小值。
输入输出样例
输入 #1
4 1 2 2 3 3 4
输出 #1
2 4
说明/提示
数据范围
对于 70\%70% 数据 n le 10^3n≤103。
对于 100\%100% 数据 n le 5 imes 10^4n≤5×104。
————————————————————————————
简单的树形DP
f[i]:i点为根的子树中所有节点到i点集中的路径总长度
cnt[i]：i点的子树内的节点数
f[i]=sum(f[son]+cnt[son])
ff[i]：表示i点集中的路径长度之和
ff[i]=ff[fa]+n-cnt[i]*2
ff[i]=f[i]+(ff[fa]-f[i]-cnt[[i])+(n-cnt[i])
上式中，f[i]孩子们在i点集中的路径长度
第一个（）内为除了i点外的所有节点在fa集中的路径长度综合
第二个（）内为fa点到i点的边要有这么多的点从这条边上向i点集中
————————————————————————————
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=5e4+10; 4 int n; 5 struct edge 6 { 7 int u,v,nxt; 8 }e[maxn<<1]; 9 int head[maxn],js; 10 void addage(int u,int v) 11 { 12 e[++js].u=u;e[js].v=v; 13 e[js].nxt=head[u];head[u]=js; 14 } 15 int f[maxn],cnt[maxn],ff[maxn]; 16 void dfs(int u,int fa) 17 { 18 cnt[u]=1;f[u]=0; 19 for(int i=head[u];i;i=e[i].nxt) 20 { 21 int v=e[i].v; 22 if(v==fa)continue; 23 dfs(v,u); 24 cnt[u]+=cnt[v]; 25 f[u]+=f[v]+cnt[v]; 26 } 27 } 28 void dfss(int u,int fa) 29 { 30 if(fa)ff[u]=ff[fa]+n-cnt[u]-cnt[u]; 31 for(int i=head[u];i;i=e[i].nxt) 32 { 33 int v=e[i].v; 34 if(v!=fa)dfss(v,u); 35 } 36 } 37 int main() 38 { 39 scanf("%d",&n); 40 for(int u,v,i=1;i<n;++i) 41 { 42 scanf("%d%d",&u,&v); 43 addage(u,v);addage(v,u); 44 } 45 dfs(1,0); 46 ff[1]=f[1]; 47 dfss(1,0); 48 int mx=ff[1],mxn=1;; 49 for(int i=2;i<=n;++i) 50 { 51 if(ff[i]<mx)mx=ff[i],mxn=i; 52 } 53 printf("%d %d",mxn,mx); 54 return 0; 55 }