换根DP

距离和

有一棵 n 个点的树，请求出每个点到其他所有点的距离的和。

定义两个点的距离为它们的简单路径上经过了多少条边。

对于整个二叉树，我们用size[i] 表示以 i 号点为根的子树中有多少个点，f[i] 表示考虑以 i 号点为根的子树，i 号点到子树中其他所有点的距离和。

对于f[i]和size[i]，直接用dfs即可做出

现在我们考虑换根，用v[i]表示i点的父亲变成子树的贡献；比如初始情况下，根节点为1，i是其子节点，现在i变为根节点，对于此时节点为1的顶点，现在他是i的儿子，那么此时以1为根的子树的贡献为v[i]=f[1]-f[i]-size[i]+n-size[i]

类比到根从x变为它的儿子y; v[y]=v[x]+f[x]-f[y]-size[y]+n-size[y]

然后分别用dfs求f[i]和v[i]就好了

int n;
ll f[100001], v[100001], size_[100001];
bool b[100001];
vector<int>son[100001];
void up(int i) {
    size_[i] = 1;
    b[i] = true;
    for (auto it : son[i]) {
        if (!b[it]) {
            up(it);
            size_[i]+=size_[it];
            f[i] += f[it];
        }
    }
    f[i] += size_[i] - 1;
}
void down(int i) {
    b[i] = true;
    for (auto it : son[i]) {
        if (!b[it]) {
            v[it] = v[i] + f[i] - f[it] - size_[it] + n - size_[it];
            down(it);
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x, y; scanf("%d %d", &x, &y);
        son[x].push_back(y);
        son[y].push_back(x);
    }
    memset(b, false, sizeof(b));
    up(1);//计算f数组
    memset(b, false, sizeof(b));
    down(1);//计算v数组
    for (int i = 1; i <= n; i++) printf("%lld\n",v[i] + f[i]);
    return 0;
}

流

有一棵 n 个点的树，每条边有一流量限制。令某一个点为根节点，向根节点灌水，最终从叶子节点流出的水量和为这一个点的最大流量，请求出每个点的最大流量。

对于整个二叉树，我们用flow[i][it]表示以 i 号点和it号点之间的流量是多少，f[i] 表示考虑以 i 号点为根的子树，i 号点的最大流量。

f[i]可用dfs算出，因为在dfs时，我们既要考虑所有儿子的流量，又要考虑自己管道本身的流量，两者取最小值，那么我们可以把叶子结点的流量初始化为无限大，然后在dfs是直接每次取最小值就好了

考虑换根，用v[i]表示i点的父亲变成子树的流量；比如初始情况下，根节点为1，i是其子节点，现在i变为根节点，对于此时节点为1的顶点，现在他是i的儿子，那么此时以1为根的子树的流量为v[i]=min(f[1]-min(f[i],flow[1][i]) ,flow [1][i]);

这里还有一种特殊情况，把根从父亲 x 号点换成儿子 y 号点后 x 号点有可能会成为新的叶子结点，这时候新的以 x 号点为根的子树最多可以承接的流量为无限大，所以最多有多少流量可以从 y 号点流到这棵子树只会被 flow[x][y] 限制，也就是说这时v[y] = flow[x][y]。然后再搜索一遍求出v[i]；注意最终流量i节点的流量是f[i]+v[i]。

int n;
ll f[100001], v[100001];
vector<int>son[100001];
map<int, int>flow[100001];
bool b[100001];
void up(int i) {
    b[i] = true;
    bool ok = true;
    for (auto it : son[i]) {
        if (!b[it]) {
            up(it);
            f[i] += min(1LL*flow[i][it],f[it]);
            ok = false;
        }
    }
    if (ok) {
        f[i] = 1 << 30;
    }
}
void down(int i) {
    b[i] = true;
    for (auto it : son[i]) {
        if (!b[it]) {
            if (v[i] + f[i] - min(f[it], 1LL * flow[i][it]))
                v[it] = min(v[i] + f[i] - min(1LL * flow[i][it], f[it]), 1LL * flow[i][it]);
            else v[it] = flow[i][it];
            down(it);
        }
    }
 
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        son[x].push_back(y);
        son[y].push_back(x);
        flow[x][y] = z; flow[y][x] = z;
    }
    memset(b, false, sizeof(b));
    up(1);
    memset(b, false, sizeof(b));
    down(1);
    for (int i = 1; i <= n; i++) {
        if (f[i] != 1 << 30) printf("%lld\n", f[i] + v[i]);
        else printf("%lld\n", v[i]);
    }
    return 0;
}