https://ac.nowcoder.com/acm/problem/13886
题意：有一颗n个点的树，n为偶数，将树上的点两两配对，两个点经过边连接，有一个距离，求这个(n/2)对点的距离最小是多少？
题解：
一棵树，必然都能相连，配对的点不要经过太多的边，避免重复导致答案太大。
对于一个点x，它子树中的点一定会尽量在子树中找到匹配的点内部消化掉（要么连父亲要么连兄弟），只有根是有可能会往上找一个点来匹配（不然又会出现重复覆盖一条边的情况）。自下而上过程中：
- 对于子树是奇数的儿子，不论是让它和兄弟配对还是和父亲配对，都要把它连上。
- 对于子树是偶数的儿子，就不用连上，因为它自己能内部消化掉了。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f using namespace std; int n,cnt; ll ans; struct Edge { int to; int val; int next; }; Edge edge[20005]; int head[10005]; void add(int u,int v,int val) { edge[cnt].to=v; edge[cnt].val=val; edge[cnt].next=head[u]; head[u]=cnt++; } int dfs(int x,int f,int val) { int sum=1;///以x为根的子树个数，自己算1个 for(int i=head[x];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=f) { sum+=dfs(v,x,edge[i].val); } } if(sum%2==1) ans+=val; return sum; } int main()///NC13886 { int t; scanf("%d",&t); while(t--) { memset(head,-1,sizeof(head)); cnt=0; ans=0; scanf("%d",&n); for(int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } dfs(1,0,0); printf("%lld ",ans); } return 0; }