[每日一题]4.2 Shortest Path

• 题意：给出一棵有偶数的节点的树，将其分成n/2对点，并且要求n/2对点的路径之和最小

• 涉及知识点：思维/树上dfs

• 思路：树上任意两点间的距离是唯一的，题目又要求路径之和最小，所以选择两个节点，要么是父节点和其孩子节点，要么是父节点的两个孩子节点，还有一种情况是多了一个孩子节点，那么肯定要先加上到父节点的距离，然后再和另外一个节点配对。
  所以在树上dfs，枚举子树的节点个数，一颗子树如果节点个数为偶数，就不需要再添加节点配对，如果节点个数为奇数，需要和父节点往外的一个节点配对，那么答案就要加上这颗子树到父节点的距离

• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  #define ll long long
  const int maxn = 10005;
  struct node{
    int t,nex;
    ll w;
  };
  node a[maxn<<1];
  int head[maxn],tot,cnt[maxn];
  ll ans ;
  void add(int x,int y,ll z){
    a[++tot].t = y,a[tot].nex = head[x],a[tot].w = z,head[x] = tot;
  }
  void dfs(int x,int fath,ll w)
  {
    cnt[x] = 1;
    for(int i=head[x] ; i ; i = a[i].nex){
        if(a[i].t != fath){
            dfs(a[i].t , x , a[i].w);
            cnt[x] += cnt[a[i].t];
        }
    }
    if(cnt[x]%2)
        ans += w;
  }
  int main()
  {
    int t;
    cin>>t;
    while(t--)
    {
        tot = 0,ans = 0;
        int n,x,y;
        scanf("%d",&n);
        memset(cnt, 0 ,sizeof(cnt));
        memset(head , 0,sizeof(head));
        for(int i=1;i<n;i++){
            ll z;
            cin>>x>>y>>z;
            add(x, y, z),add(y, x, z);
        }
        dfs(1 , 0 , 0);
        cout<<ans<<endl;
    }
    return 0;
  }
  

```