CF图论2000分
题意：t组数据，给出k对人，你需要将他们放到有2k个节点的树上，给出了2k-1条边和边权，问每对人之间的距离和的最大值和最小值
解法：求最小值的情况：看每个点的儿子的siz，如果是奇数，就把这条边的w加上。因为选择的原理是取最近的选。如果一个节点连了偶数个未被算的节点（不算上父节点），那么显然这偶数个节点互相连接最小。如果一个节点连了奇数个还未被算的节点（不算父节点），那么显然这个节点和他连着的节点相连更小。dfs即可
求最大值的情况：
方法1：计算每一条边的贡献，随便选择一个点作为root开始，然后根据这条边的u和v的siz情况来看，每条边的贡献即为w*min(siz[v],n-siz[v])，最后把每个边的贡献加起来即可。
方法2：找到树的重心，然后每个节点到重心的距离加起来即为最大值。
AC代码：
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl '\n' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=3e5+5; int tot,head[maxn]; struct E{ int to,next,w; }edge[maxn<<1]; void add(int u,int v,int w){ edge[tot].to=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } int siz[maxn],n;ll ans1,ans2; void dfs(int x,int fa){ siz[x]=1; for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].to,w=edge[i].w; if(v==fa) continue; dfs(v,x); siz[x]+=siz[v]; if(siz[v]%2==1) ans1+=w; ans2+=1LL*w*min(n-siz[v],siz[v]); } } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d",&n);n*=2; mem(head,-1);tot=0;mem(siz,0); ans1=ans2=0; rep(i,1,n-1){ int u,v,w;scanf("%d%d%d",&u,&v,&w); add(u,v,w);add(v,u,w); } dfs(1,0); printf("%lld %lld\n",ans1,ans2); } }