12-动态规划/04-树上DP

树上 DP

在树上进行动态规划，利用树的递归结构，通常使用 DFS 实现。

子树大小

vector<int> g[MAXN];
int sz[MAXN];

void dfs(int u, int fa)
{
    sz[u] = 1;
    for (int v : g[u])
        if (v != fa)
        {
            dfs(v, u);
            sz[u] += sz[v];
        }
}

树的直径

树中距离最远的两个点之间的距离。

两次 BFS/DFS 法

int dis[MAXN], far;

// 从任意点出发找最远点 far
void dfs(int u, int fa)
{
    for (int v : g[u])
        if (v != fa)
        {
            dis[v] = dis[u] + 1;
            if (dis[v] > dis[far]) far = v;
            dfs(v, u);
        }
}

// 调用
far = 1;
dfs(1, 0);      // 第一次任意起点
int a = far;
dis[a] = 0;
dfs(a, 0);      // 第二次从最远点出发
int b = far;
// dis[b] 即为直径长度

树形 DP 法

int ans = 0;

// 返回以 u 为起点的最长向下路径长度
int dfs(int u, int fa)
{
    int max1 = 0, max2 = 0;
    for (int v : g[u])
        if (v != fa)
        {
            int d = dfs(v, u) + 1; // +1 = 边权
            if (d > max1) { max2 = max1; max1 = d; }
            else if (d > max2) { max2 = d; }
        }
    ans = max(ans, max1 + max2); // 经过 u 的最长路径
    return max1;
}

树的重心

删除重心后，剩余每个连通分量的大小都不超过 [math]\displaystyle{ n/2 }[/math]。

int centroid, sz[MAXN];

void dfs(int u, int fa)
{
    sz[u] = 1;
    int max_part = 0;
    for (int v : g[u])
        if (v != fa)
        {
            dfs(v, u);
            sz[u] += sz[v];
            max_part = max(max_part, sz[v]);
        }
    max_part = max(max_part, n - sz[u]); // 父节点方向的分量
    if (max_part <= n / 2)
        centroid = u; // 可以存在两个重心
}