牛客每日一题4.3 Shortest Path 树dp

https://blog.csdn.net/qq_43804974/article/details/105269874
首先这个数据范围，看着就是O(N)或者O（Nlogn）的东西，考虑树dp。
先贪心的考虑。一个点怎么找到另一个点？肯定是他能接触到的最短的那个点，如果与他最短的那个点被用过了呢？找其他第二近的点，以此类推。
对于一个点，是只有当找不到人了才会继续走上去找其他人匹配，不然不管多大的权值都是会跟那个人走的。因为对于一条权值很大的边，边连着的两个点如果深度深的点在往下匹配不到人，就必须走上匹配，最少需要经过这条边一次，那么对于一个必须经过这个边的点他肯定是与另一个无法匹配的点去结合，不管这个权值多大大你都必须走这条边。

就像这个图，你 2-3和2-4的边是必须走，是永远无法避开的。因为节点3往下找不到点跟他匹配，这条998的边必须走。

这里树dp要去考虑边对答案的贡献跟一般的考虑点的贡献不太一样，我们只需要算每条边产生多少贡献，也就是每条边会有多少个点对需要用到他。
f[i]就是以i的子树的所有边产生的贡献。

f[i] = sum(f[to]) + sum（v）；

这个v是什么？如果size【to】（以to为根的子树的孩子数量）是奇数，那么必然存在一个点是没有匹配的对象，需要往上走，那么往上走就必然需要经过这条边，则吧这条边的贡献加上。最后输出f【1】就是所有边产生的贡献，也就是答案。

int n,son[max_],f[max_];
vector<pair<int, int> > xian[max_];
void dfs(int now, int fa) {
    son[now] = 1;
    for (auto pa : xian[now]) {
        int to = pa.first, v = pa.second;
        if (to == fa)continue;
        dfs(to, now);
        son[now] += son[to];
        f[now] += f[to];
        if (son[to] % 2)f[now] += v;
    }
}
signed main() {
    int T ;
    cin >> T;
    while (T--){
        n = read();
        for (int i = 0; i <= n; i++)xian[i].clear(), f[i] = son[i] = 0;
        for (int i = 2; i <= n; i++) {
            int a = read(), b = read(), c = read();
            xian[a].push_back(make_pair(b, c));
            xian[b].push_back(make_pair(a, c));
        }
        dfs(1, 0);
        cout << f[1] << endl;
    }
    return 0;
}