树形DP模型

树的最长路径

题目描述：

给定一棵树，树中包含 $n$ 个结点（编号 $1$ ~ $n$ ）和 $n - 1$ 条无向边，每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说，要找到一条路径，使得路径两端的点的距离最远。

注意：路径中可以只包含一个点。

输入格式：

第一行包含整数 $n$ 。

接下来 $n - 1$ 行，每行包含三个整数 $a_i , b_i , c_i$ ，表示点 $a_i$ 和 $b_i$ 之间存在一条权值为 $c_i$ 的边。

输出格式：

输出一个整数，表示树的最长路径的长度。

数据范围：

$1 \leq n \leq 10000$

$1 ≤ a_i, b_i ≤ n$

$10^5 ≤ c_i ≤ 10^5$

输入样例：

输出样例：

代码实现

在这里插入图片描述

因此找次长和最长组成最长路径的答案

力扣相似题目

import sys
input = sys.stdin.readline

n = int(input().strip())
g = [[] for _ in range(n)]

for i in range(n - 1):
    a, b, c = map(int, input().strip().split())
    g[a - 1].append((b - 1, c))
    g[b - 1].append((a - 1, c))

ans = 0  # 记录最长路径答案


def dfs(x, fa):
    global ans
    max_val = 0  # 找子树最大链长
    for y, val in g[x]:
        if y == fa:  # 跳过祖先节点
            continue
        next_val = dfs(y, x) + val  # 当前枚举的子节点链长
        ans = max(max_val + next_val, ans)  # 将先前的最大链长 + 枚举的子节点链长
        max_val = max(max_val, next_val)  # 更新子树最大链长
    return max_val


dfs(0, -1)
print(ans)

*树的中心

题目描述：

给定一棵树，树中包含 $n$ 个结点（编号 $1$ ~ $n$ ）和 $n - 1$ 条无向边，每条边都有一个权值。

请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。

输入格式：

第一行包含整数 $n$ 。

接下来 $n - 1$ 行，每行包含三个整数 $a_i , b_i , c_i$ ，表示点 $a_i$ 和 $b_i$ 之间存在一条权值为 $c_i$ 的边。

输出格式：

输出一个整数，表示所求点到树中其他结点的最远距离。

数据范围：

$1 \leq n \leq 10000$

$1 ≤ a_i, b_i ≤ n$

$1 ≤ c_i ≤ 10^5$

输入样例：

输出样例：

换根dp的理解

换根dp的经典题目

大佬的题解

妙！
在这里插入图片描述

代码实现

import sys
input = sys.stdin.readline

n = int(input().strip())
g = [[] for _ in range(n)]

for i in range(n - 1):
    a, b, c = map(int, input().strip().split())
    g[a - 1].append((b - 1, c))
    g[b - 1].append((a - 1, c))

# ans   -记录当前节点的到其他节点的最远距离
# size  -记录当前节点的子节点数量
ans, size = [0] * n, [1] * n

# 计算 0 节点的到树中其他结点的最远距离
def dfs(x, fa):
    res = 0
    for y, val in g[x]:
        if y == fa:
            continue
        res += dfs(y, x) + val
        size[x] += size[y]
    ans[0] += res
    return res

dfs(0, -1)

# 通过 0 节点更新其他节点的到树中其他结点的最远距离（换根）
def reroot(x, fa):
    for y, val in g[x]:
        if y == fa:
            continue
        ans[y] = ans[x] + val * (n - 2 * size[y])
        reroot(y, x)


reroot(0, -1)
print(ans.index(min(ans)) + 1)

数字转换

题目描述：

如果一个数 $x$ 的约数之和 $y$ （不包括它本身）比它本身小，那么 $x$ 可以变为 $y$ ， $y$ 也可以变为 $x$ 。

例如， $4$ 可以变为 $3$ ， $1$ 可以变为 $7$ 。

限定所有数字变换在不超过 $n$ 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。

输入格式：

输入一个正整数 $n$ 。

输出格式：

输出不断进行数字变换且不出现重复数字的最多变换步数。

数据范围：

$1 \leq n \leq 50000$

输入样例：

输出样例：

样例解释：
一种方案为： $4 \to 3 \to 1 \to 7$

代码实现

以题目 x 与 y 的关系进行建图

再以 1 为起点找最大直径

为什么找 $1$ ，因为 $1$ 可以将绝大部分数字串起来，最优解一定出现在含 $1$ 的树上。

另外，以 $x$ 和 $y$ 关系建立的不是树，而是森林。例如 $6$ 的约数之和还是为 $6$ ，故 $6$ 单独在一个树上。

import sys
input = sys.stdin.readline

n = int(input().strip())
g = [[] for _ in range(n + 1)]

for i in range(2, n + 1):
    j, sum_val = 2, 1
    while j <= i // j:
        if i % j:
            j += 1
            continue
        if j * j == i:
            sum_val += j
        else:
            sum_val += j + i // j
        j += 1
    g[sum_val].append(i)
    g[i].append(sum_val)


ans = 0
def dfs(x, fa):
    global ans
    max_val = 0
    for y in g[x]:
        if y == fa:
            continue
        val = dfs(y, x) + 1
        ans = max(ans, max_val + val)
        max_val = max(max_val, val)

    return max_val


dfs(1, -1)
print(ans)

*二叉苹果树

题目描述：

有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。

这棵树共 $N$ 个节点，编号为 $1$ 至 $N$ ，树根编号一定为 $1$ 。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。

一棵苹果树的树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

这里的保留是指最终与 $1$ 号点连通。

输入格式：

第一行包含两个整数 $N$ 和 $Q$ ，分别表示树的节点数以及要保留的树枝数量。

接下来 $N - 1$ 行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。

输出格式：

输出仅一行，表示最多能留住的苹果的数量。

数据范围：

$1 \leq Q < N \leq 100$ ， $N \neq = 1$ ，每根树枝上苹果不超过 $30000$ 个。

输入样例：

输出样例：

代码实现

跟背包问题DP模型中的有依赖的背包问题同样处理

import sys
input = sys.stdin.readline

n, q = map(int, input().strip().split())
g = [[] for _ in range(n)]

for _ in range(n - 1):
    a, b, c = map(int, input().strip().split())
    g[a - 1].append((b - 1, c))
    g[b - 1].append((a - 1, c))

f = [[0] * (q + 1) for _ in range(n)]


def dfs(x, fa):
    for y, val in g[x]:
        if y == fa:
            continue
        dfs(y, x)
        
        # 由于子树遍历
        # 逆向更新防止更新两次
        for i in range(q, 0, -1):
            for j in range(i):
                f[x][i] = max(f[x][i], f[x][i - 1 - j] + f[y][j] + val)


dfs(0, -1)
print(f[0][-1])

*保安站岗

题目描述：

五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。

已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。

一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。

编程任务：

请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。

输入格式：

第 $1$ 行 $n$ ，表示树中结点的数目。

第 $2$ 行至第 $n + 1$ 行，每行描述每个通道端点的信息，依次为：该结点标号 $i$ （ $\le n$ ），在该结点安置保安所需的经费 $k$ （ $\leq 10000$ ），该边的儿子数 $m$ ，接下来 $m$ 个数，分别是这个节点的 $m$ 个儿子的标号 $r_1,r_2,\cdots, r_m$ 。

对于一个 $n$ （ $\le 1500$ ）个结点的树，结点标号在 $1$ 到 $n$ 之间，且标号不重复。

输出格式：

输出一行一个整数，表示最少的经费。

样例 #1

样例输入 #1

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

样例输出 #1

提示

样例解释

在结点 $2, 3, 4$ 安置 $3$ 个保安能看守所有的 $6$ 个结点，需要的经费最小： $25$ 。

代码实现

import sys
from math import inf
sys.setrecursionlimit(1000000)
input = sys.stdin.readline


n = int(input().strip())
g = [[] for _ in range(n + 1)]
cost = [0] * (n + 1)

for _ in range(n):
    nums = list(map(int, input().strip().split()))
    a = nums[0]
    cost[a] = nums[1]
    for b in nums[3:]:
        g[a].append(b)
        g[b].append(a)


def dfs(x, fa):
    choose, by_fa, by_children = cost[x], 0, inf
    for y in g[x]:
        if y == fa:
            continue
        y_choose, y_by_fa, y_by_children = dfs(y, x)
        choose += min(y_choose, y_by_fa)
        by_fa += min(y_choose, y_by_children)
        by_children = min(by_children, y_choose - y_by_children)
    by_children = max(0, by_children) + by_fa
    return choose, by_fa, by_children


choose, _, by_children = dfs(1, -1)
print(min(choose, by_children))

扩展练习

监控二叉树

二叉树灯饰

二叉树染色

战略游戏

题目背景：

Bob 喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。

题目描述：

他要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。

注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。

请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。

输入格式：

第一行一个整数 $n$ ，表示树中结点的数目。

第二行至第 $n + 1$ 行，每行描述每个结点信息，依次为：一个整数 $i$ ，代表该结点标号，一个自然数 $k$ ，代表后面有 $k$ 条无向边与结点 $i$ 相连。接下来 $k$ 个整数，分别是每条边的另一个结点标号 $r_1,r_2,\cdots,r_k$ ，表示 $i$ 与这些点间各有一条无向边相连。

对于一个 $n$ 个结点的树，结点标号在 $0$ 到 $n - 1$ 之间，在输入数据中每条边只出现一次。保证输入是一棵树。

输出格式：

输出文件仅包含一个整数，为所求的最少的士兵数目。

样例 #1

样例输入 #1

样例输出 #1

提示：

数据规模与约定

对于全部的测试点，保证 $\leq n \leq 1500$ 。

代码实现

与保安站岗不同的是，战略游戏中由于是看边关系。父节点监控不到子节点与孙子节点之间连的边，因此只需要两个自变量进行即可。

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline


n = int(input().strip())
g = [[] for _ in range(n)]

for _ in range(n):
    nums = list(map(int, input().strip().split()))
    a = nums[0]
    for b in nums[2:]:
        g[a].append(b)
        g[b].append(a)


def dfs(x, fa):
    choose, no_choose = 1, 0
    for y in g[x]:
        if y == fa:
            continue
        y_choose, y_no_choose = dfs(y, x)
        choose += min(y_choose, y_no_choose)
        no_choose += y_choose

    return choose, no_choose

print(min(dfs(0, -1)))

皇宫看守

题目描述：

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。

皇宫各个宫殿的分布，呈一棵树的形状，宫殿可视为树中节点，两个宫殿之间如果存在道路直接相连，则该道路视为树中的一条边。

已知，在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况，还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。

大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。

帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入格式：

输入中数据描述一棵树，描述如下：

第一行 $n$ ，表示树中节点的数目。

接下来 $n$ 行，每行描述每个宫殿节点信息，依次为：该宫殿节点标号 $i$ ，在该宫殿安置侍卫所需的经费 $k$ ，该节点的子节点数 $m$ ，接下来 $m$ 个数，分别是这个节点的 $m$ 个子节点的标号 $r_1, r_2, …, r_m$ 。

对于一个 $n$ 个节点的树，节点标号在 1 到 n 之间，且标号不重复。

输出格式：

输出一个整数，表示最少的经费。

数据范围：

$1 \leq n \leq 1500$

输入样例：

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

输出样例：

代码实现

与保安站岗同一做法

import sys
from math import inf
input = sys.stdin.readline

n = int(input().strip())
g = [[] for _ in range(n)]
cost = [0] * n

for _ in range(n):
    line = list(map(int, input().strip().split()))
    a = line[0]
    cost[a - 1] = line[1]
    for b in line[3:]:
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)


def dfs(x, fa):
    choose, by_fa, by_son = cost[x], 0, inf
    for y in g[x]:
        if y == fa:
            continue
        y_choose, y_by_fa, y_by_son = dfs(y, x)
        choose += min(y_choose, y_by_fa)
        by_fa += min(y_choose, y_by_son)
        by_son = min(by_son, y_choose - y_by_son)
    by_son = max(0, by_son) + by_fa
    return choose, by_fa, by_son

choose, _, by_son = dfs(0, -1)
print(min(choose, by_son))