查看“︁12-动态规划/04-树上DP”︁的源代码


== 树上 DP ==

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

== 子树大小 ==

<syntaxhighlight lang="cpp">
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];
        }
}
</syntaxhighlight>

== 树的直径 ==

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

=== 两次 BFS/DFS 法 ===

<syntaxhighlight lang="cpp">
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] 即为直径长度
</syntaxhighlight>

=== 树形 DP 法 ===

<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

== 树的重心 ==

删除重心后，剩余每个连通分量的大小都不超过 <math>n/2</math>。

<syntaxhighlight lang="cpp">
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; // 可以存在两个重心
}
</syntaxhighlight>

[[Category:动态规划]]
[[Category:三三文档]]