【每日一题】转换思维/树上dfs

https://ac.nowcoder.com/acm/problem/13886

是我最喜欢的树上dfs~
给你一棵 n 个节点的树（保证 n是偶数），你需要将 nn个节点分为 n/2 个点对，使得每个点对的两个点的距离的和最小。

关键点：思维转换:选点两两配对求距离和--》转换成选边

• 在最短的距离和之中一条边一定不会被覆盖两次,也就是说对于一条边来说，其实只有选和不选两种可能。
• 对于一个点x，它子树中的点一定会尽量在子树中找到匹配的点内部消化掉（要么连父亲要么连兄弟），只有根是有可能会往上找一个点来匹配（不然又会出现重复覆盖一条边的情况）。
  这道题最关键的是转换思维，如果考虑两两配对并不容易编码，而是直接考虑边，边只有选和不选两种可能；
  对于当前点 x，如果它的子树（包括它自己）有偶数个点，那么肯定在子树里面就互相连完了，它不需要向上连；如果是奇数个点，x 就需要去匹配上面的点了，所以 x向它父亲连的边就要选。

  #include<bits/stdc++.h>
  using namespace std;
  #define ll long long
  #define MAXN 20010
  ll p[MAXN],h[MAXN],ne[MAXN],edgew[MAXN]; ll num=0;
  void addEdge(int from, int to,int w)
  {
    p[++num] = to;
    ne[num] = h[from];
    h[from] = num;
    edgew[num] = w;
    p[++num] = from;
    ne[num] = h[to];
    h[to] = num;
    edgew[num] = w;
  }
  ll ans=0;
  ll cnt[MAXN>>1];//记录子树的节点数量
  void dfs(int u,int father,int faw){
    cnt[u]=1;
    for(int i=h[u];i;i=ne[i])if(p[i]!=father)
    {
        dfs(p[i],u,edgew[i]);
        cnt[u]+=cnt[p[i]];
    }
    if(cnt[u]&1) ans+=faw;//加上和父亲的边
  }
  int main()
  {
    int t;
    cin>>t;
    while(t--)
    {
        ans = 0;
        num=0;
        int n;cin>>n;
        memset(h, 0, sizeof(h));
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= n-1; i++)
        {
            int x,y,w;
            scanf("%d%d%d", &x, &y, &w);
            addEdge(x, y, w);
        }
        dfs(1, 0, 0);
        printf("%lld\n", ans);
    }
  }