python/TangDou/Topic/【树上DP前导知识汇总】.md

一、树的直径

记录最长、次长，输出 max(最长+次长)

AcWing 1072 树的最长路径

#include <bits/stdc++.h>

using namespace std;
const int N = 10010, M = N << 1;
int n; // n个结点

// 链式前向星
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int ans;            // 答案,直径
int mx1[N], mx2[N]; // mx1[i],mx2[i]:经过i点的最长,次长长度是多少

void dfs(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue; // v点访问过了

        // 走v子树,完成后，v子树中每个节点的mx1[v],mx2[v]都已经准备好，u节点可以直接利用
        dfs(v, u);

        // w[i]:u->v的路径长度,mx1[u]:最长路径,mx2[u]:次长路径
        int x = mx1[v] + w[i];
        if (mx1[u] <= x)                 // v可以用来更新u的最大值
            mx2[u] = mx1[u], mx1[u] = x; // 最长路转移
        else if (mx2[u] < x)
            mx2[u] = x; // 次长路转移
    }
    // 更新结果
    ans = max(ans, mx1[u] + mx2[u]);
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);      // 初始化邻接表
    for (int i = 1; i < n; i++) { // n-1条边
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c); // 换根dp一般用于无向图
    }
    dfs(1, 0); // 任选一个点作为根节点,此处选择的是肯定存在的1号结点
    cout << ans << endl;
    return 0;
}

二、树的中心

AcWing 1073. 树的中心

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, M = N << 1;
const int INF = 0x3f3f3f3f;

int n;      // n个节点
int mx1[N]; // mx1[u]：u节点向下走的最长路径的长度
int mx2[N]; // mx2[u]：u节点向下走的次长路径的长度
int id[N];  // id[u]：u节点向下走的最长路径是从哪一个节点下去的
int up[N];  // up[u]：u节点向上走的最长路径的长度

// 邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 功能:以u为根，向叶子进行递归，利用子节点返回的最长信息，更新自己的最长和次长,并记录最长是从哪个节点来的
void dfs1(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;

        // 递归完才能有数据
        dfs1(v, u);
        int x = mx1[v] + w[i]; // u问到：儿子v可以带我走多远？
        if (mx1[u] < x) {      // 更新最长
            mx2[u] = mx1[u];   // ① 更新次长
            mx1[u] = x;        // ② 更新最长
            id[u] = v;         // ③ 记录最长来源
        } else if (mx2[u] < x) // 更新次长
            mx2[u] = x;
    }
}

// 功能：完成向上的信息填充
void dfs2(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        // 二者取其一
        if (id[u] == v)
            up[v] = max(mx2[u], up[u]) + w[i];
        else
            up[v] = max(mx1[u], up[u]) + w[i];
        // 递归
        dfs2(v, u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    dfs1(1, 0); // 选择任意一个节点进行dfs,用儿子更新父亲的统计信息
    dfs2(1, 0); // 向上

    int res = INF;
    for (int i = 1; i <= n; i++) res = min(res, max(mx1[i], up[i]));
    printf("%d\n", res);

    return 0;
}

三、树的重心

CF1406C. Link Cut Centroids

账号：10402852@qq.com 密码：m****2 关键词：求树的重心

题目大意 给你一棵树的结点数n和n-1条边，你可以删除一条边再增加一条边，使得树的重心唯一,输出这条边

注意：有Specail Judge，如果删除哪条都行，那就随意删除一条就行

告诉你的已知性质： ① 删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心 ② 树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等 ③ 两个树通过一条边合并，新的重心在原树两个重心的路径上 ④ 树删除或添加一个叶子节点，重心最多只移动一条边 ⑤ 一棵树最多有两个重心，且相邻

树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点1后，树将分成两个连通块：(2,4,5)，(3,6,7)，则最大的连通块包含节点个数为3。若去掉点2，则树将分成3个部分，(4)，(5)，(1,3,6,7)最大的连通块包含4个节点；第一种方法可以 得到更小的最大联通分量。可以发现，其他方案不可能得到比3更小的值了。所以，点1是树的重心。

思路

• 如果找到只有一个重心，那么直接删一个重心的直连边然后加回去就好
• 如果找到两个重心，那么在其中一个重心上找到一个直连点不是另一个重心，删除连另外一个就好

如何求树的重心？

1、先任选一个结点作为根节点(比如1号节点)，把无根树变成有根树。然后设sz[i]表示以i为根节点的子树节点个数。转移方程为\displaystyle sz[u]=\sum_{son[u]=v} (sz[v])

2、设son[i]表示删去节点u后剩下的连通分量中最大子树节点个数。其中一部分在原来i其为根的子树。

son[i]=\max_{\substack{j \in son[i]}}(son[i],sz[j])

另外一部分在i的 上方 子树有n-sz[i]个。

son[i]=max(son[i],n-sz[i])

3、利用重心性质： ① 树必须存在1或2个重心 , ② 如果某个点是重心，那么把它拿下后，其它连通块的个数都需要小于等于整棵树节点个数的一半。 满足条件 ② 的结点数量不会超过2个！分别记录为r_1,r_2。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N << 1;
#define int long long
#define endl "\n"

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int sz[N];  // sz[i]:以i为根的子树中节点个数
int son[N]; // son[i]:去掉节点i后，剩下的连通分量中最大子树节点个数
int r1, r2, n;

void dfs(int u, int fa) {
    sz[u] = 1;  // u为根的子树中，最起码有一个节点u
    son[u] = 0; // 把节点u去掉后，剩下的连通分量中最大子树节点个数现在还不知道，预求最大，先设最小

    for (int i = h[u]; ~i; i = ne[i]) { // 枚举u的每一条出边
        int v = e[i];
        if (v == fa) continue;
        dfs(v, u);                   // 先把v为根的子树遍历完
        sz[u] += sz[v];              // 把 v中获取填充的sz[v]值，用于组装自己sz[u]
        son[u] = max(son[u], sz[v]); // 如果把u节点去掉，那么它的所有子节点v为根的子树中节点数，可以参加评选：
        // 评选的标准是：son[i]:去掉节点i后，剩下的连通分量中最大子树节点个数
    }
    son[u] = max(son[u], n - sz[u]);         // 右上角的那一块也可能成为评选的获胜者
    if ((son[u] << 1) <= n) r2 = r1, r1 = u; // 删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心
    // 如果模拟u被删除后，得到的所有子树中节点数量最多的没有超过原树的1/2,那么这个r1=u表示：找到了一个重心u
    // r2=r1表示：如果找到两个重心，那么r1,r2 一人一个，此时，r1中肯定有值，但 r2不一定有值
}

signed main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        // 多组测试数据，清空
        memset(sz, 0, sizeof sz);
        memset(son, 0, sizeof son);
        // 初始化链式前向星
        memset(h, -1, sizeof h);
        idx = 0;

        r1 = r2 = 0;                  // 重心清零
        for (int i = 1; i < n; i++) { // n-1条边
            int x, y;
            cin >> x >> y;
            add(x, y), add(y, x);
        }
        dfs(1, 0); // 以1号点为入口，它的父节点是0

        if (r2 == 0) { // 如果只有一个重心，r2=0表示没有第二个重心
            int u = r1, v = e[h[u]];
            cout << u << " " << v << endl; // 切掉一条边u->v
            cout << u << " " << v << endl; // 加一条边 u->v
        } else {                           // 如果有两个重心
            int u = r2, v;
            for (int i = h[u]; ~i; i = ne[i]) { // 不要删除掉两个重心相连接的那条边
                v = e[i];
                if (v != r1) break; // 只要对方节点不是另一个重心，那么就是可以删除的
            }
            cout << u << " " << v << endl;  // 切一条边u->v，第二个重心所在边需要被切掉
            cout << v << " " << r1 << endl; // 加一条边v->r1,不走u了，走了u的一个子节点v
        }
    }
    return 0;
}