33DAI：批量导入三三文档

2026-05-20T18:24:10Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第100行：		第100行：
	[[Category:动态规划]]		[[Category:动态规划]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:28Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 树上 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:三三文档]]

12-动态规划/04-树上DP - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档