题目

题目描述：
F（x）是一种属性。F（x）（节点x的累积度）定义如下：
  1. 树的每个边缘的权值是一个整数。
  2. 树中度为1的节点称为终端。
  3. 每条边的流量不能超过其权值。
  4. F（x）是节点x可以流到其他终端节点的最大流。
求在哪个节点积累度最大。（样例详情看原题）

输入描述： 
输入的第一行是整数T，它表示测试用例的数量。每个测试用例的第一行是一个正整数n。
接下来的n-1行中的每行包含三个由空格分隔的整数x，y，z，表示节点x和y之间存在边，并且边的容量为z。节点从1到n编号。
所有元素都是不超过200000的非负整数。您可以假定测试数据都是树度量。 

输出描述：
 对于每个测试用例，将结果单行输出。

解析

hanhan因为刚刚做完了树学这道题，所以对这个题目也有了一定的了解，推出了公式，但是还是有点不会写，orz
首先还是日常的操作步骤：
  1. 基本操作，用树的孩子表示法存储好树结构。
  2. 接下来我们就要求出每个节点做根时的最大流。
  3. 最后找最大的输出就行了。
那么最重要的就是这里了，我们该怎么求出每个节点的最大流呢？
正常操作，直接遍历，1000%就TLE了。所以我们就要想到求出递推式，用树形dp算法得到答案。

我们这里分两步进行操作：
  1. 递归+递推得出每个节点为根的最大流。（存入dp）
  2. 树形dp递推得出以每个节点为根节点产生的最大流。（存入Flow）
（ps：这两个说法很接近，但是完全不一样，见图解）
接下来就是求出递推公式了：

每个节点为根的最大流（dp数组）获得：
  1. 各节点为根的最大流的递推公式不难得出：dp[i]=∑min(dp[j],edge[i][j])（ j 是 i 的子节点，dege[i][j]指 i 与 j 之间的距离）
  2. 但是在代码中我们要进行一些变换了：（我们将子节点简化为son）
  3. 当son的度=1时（son为终端的时候）dp[root] += dege(root,son) ：没有该节点没有son了。
  4. 当son的度>1时dp[root] += min( dp[son],e(root,son) ) ：
    首先是+=，因为可能有多个son，要做一个循环累加；然后右式的意思是选取，每一个son的最小流，和能通过的流量中的较小值。（因为超过了流量也流不过去）

每个节点为根节点产生的最大流（Flow数组）获得：
  1. 怎么来的呢，我们可以简单地推出来：当子节点变成根时，该子树的最大流不变，由于倒置，父节点将会产生一个新的流：Flow[x]−min(Flow[y],edge[x][y])。（x原来的总流-y所在的流）
  2. 亮出我们的最终方程Flow[y]=Flow[y]+min(Flow[x]−min(Flow[y],edge[x][y]),edge[x][y])。
  3. 在图解里引用一下邓老师的图，超好理解。

图解

  1. 是求该分支的最大流。（圈起来的子树）
  2. 是求该节点做根节点时的最大流。（转化后的树）

AC代码 

#include <iostream>
#include <vector>
using namespace std;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAX = 2e5 + 7;
typedef struct {
    int bro, weight;//与该节点相连的节点，边的权重
} Node;
vector<Node> Tree[MAX];//树的孩子表示法
int Flow[MAX], dp[MAX], degree[MAX], visited[MAX];
//Flow[i]表示以i为根的最大流量；dp[i]为i的子树的最大流量；degree表示每个结点的度；visited是探测数组

void dfs(int x);//初始化depth数组和cnt数组
void solve(int x);//求出每个点做根时的最大流量（F)

int main() {
    js;
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        memset(degree, 0, sizeof(degree));
        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= n; i++)
            Tree[i].clear();
        //初始化
        for (int i = 0; i < n - 1; i++) {
            int x, y, z; cin >> x >> y >> z;
            degree[x]++; degree[y]++;
            Tree[x].push_back({ y, z  });
            Tree[y].push_back({ x, z  });
        }
        //树的孩子表示法初始化
        dfs(1);
        memset(visited, 0, sizeof(visited));
        Flow[1] = dp[1];
        solve(1);
                //计算出每个节点做根的情况存入Flow
        int max = 1;
        for (int i = 2; i <= n; i++)
            if (Flow[max] < Flow[i])
                max = i;
                //选出其中的最大值
        cout << Flow[max] << endl;
    }
    return 0;
}

void dfs(int x) {
    visited[x] = 1;
    dp[x] = 0;
    for (auto c : Tree[x])
        if (!visited[c.bro]) {
            dfs(c.bro);
            if (degree[c.bro] == 1) dp[x] += c.weight;
            else dp[x] += min(c.weight, dp[c.bro]);
            //分类讨论的原因是，度为1的节点的dp值为0，和取较小值互斥
        }
}
void solve(int x) {
    visited[x] = 1;
    for (auto c : Tree[x])
        if (!visited[c.bro]) {
            if (degree[x] == 1) Flow[c.bro] =  dp[c.bro] + c.weight;
            else Flow[c.bro] = dp[c.bro] + min(Flow[x] - min(dp[c.bro], c.weight), c.weight);
                        //将某个节点变成根，并计算的操作
            solve(c.bro);
        }
}