给出一棵n个点的树，将这n个点两两配对，求所有可行的方案中配对两点间的距离的总和最大为多少。 Input 一个数n（1<=n<=100,000,n保证为偶数） 接下来n-1行每行三个数x,y,z表示有一条长度为z的边连接x和y（0<=z<=1,000,000,000） Output 一个数表示答案 Sample Input 6 1 2 1 1 3 1 1 4 1 3 5 1 4 6 1 Sample Output 7 //配对方案为（1，2）（3，4）（5，6）
考虑每一条边。它的贡献就是它的权值与它出现的次数的乘积。 理论上来说，设断开这条边后连通块的大小分别为s1,s2,最大贡献值就是 z × m i n ( s 1 , s 2 ) z \times min(s1,s2) z×min(s1,s2)。 然后让每条路径经过重心，就可以凑（？）出这个理论值。原因？不太清楚。
为了定义树的重心，需要给树的每一个顶点赋上一个权值。考虑顶点k。如果从图中删除k号顶点(连带的边也一起被删除)，剩下的图将只有 N-1 个顶点而且可能由多个连通分量组成。显然每一个连通分量还是一棵树。那么k号顶点的权值就是删除它以后剩下的连通分量中顶点数最多的顶点个数。 这 N 个顶点中权值最小的就是重心。
又参考了某个同学的题解，没有求重心，直接一边dfs一边计算。 详见代码。
#include<cstdio> #include<vector> #include<algorithm> #define maxn 100005 using namespace std; int n,siz[maxn]; long long ans; struct node { int to,cost; }; vector<node> G[maxn]; void dfs(int u,int fa) { siz[u]=1; for(int i=0;i<G[u].size();i++) { int v=G[u][i].to,w=G[u][i].cost; if(v==fa) continue; dfs(v,u); siz[u]+=siz[v]; ans+=1ll*w*min(siz[v],n-siz[v]); } } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int u;node e; scanf("%d%d%d",&u,&e.to,&e.cost); G[u].push_back(e); swap(u,e.to); G[u].push_back(e); } dfs(1,0); printf("%lld\n",ans); }