换根DP ( 树形DP )
确定了根节点之后,对于每一个节点u
,预处理两个值:每个节点往下可以传递到的节点的数量down[u]
,和每个节点往上可以传递到的节点的数量up[u]
那么节点u
可以传递到的节点的总数就是:down[u] + up[u]
因此只要预处理出了这两个数组,对于所有节点的down[u] + up[u]
取max
就是最终答案。
换根DP的精髓在于,如何dfs两次就可以预处理出这两个信息:$\mathcal O(n)$
假设存在u -> j
的边,那么:
down[]
—— 自底向上
down[u]
初始为1
down[u] += down[j]
( 前提:w[u] > w[j]
)
up[]
—— 自项向下
up[j] = up[u] + (down[u] - u -> j 分支可以往下传递的节点数量)
:子节点往上可以传递的节点数量 = 父节点往上可以传递的节点数量 + 父节点往下可以传递的节点数量 - 父节点往下经过j
可以传递的节点数量
由于转移的条件是w[j] > w[u]
,此时down[u]
本身就不存在u -> j
分支,因此可以直接用down[u]
转移
小细节:
down[]
计算的时候包含u
这个节点,up[]
不包含。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010, M = N << 1;
int n;
int h[N], e[M], ne[M], idx;
int w[N];
int down[N], up[N];
/*
1. down[u] 表示每个节点 往下 可以传递的节点数量 ( 包括 u 本身 )
2. up[u] 表示每个节点 往上 可以传递的节点的数量 ( 不包括 u 本身 )
*/
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs_d(int u, int fa)
{
down[u] = 1; // 包括 u 这个节点
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
int d = dfs_d(j, u);
if (w[u] <= w[j]) d = 0; // d = 0 表示不存在这个分支
down[u] += d;
}
return down[u];
}
void dfs_u(int u, int fa)
{
// up[u] = 0; // 不包括 u 这个节点
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
// 树中每个节点的父节点是唯一的 —— up[j] 只由 up[u] 转移
if (w[j] > w[u]) up[j] = up[u] + down[u];
else up[j] = 0; // w[j] <= w[u] // 多组数据!不能省略!
// 子节点往上可以传递到的节点数量 =
// 父节点往上可以传递到的节点数量 +
// 父节点往下且不经过 j 可以传递到的节点数量 ( w[j] > w[u] —— down[u] 不包括 u -> j 的分支)
dfs_u(j, u);
// printf("u = %d, down[u] = %d\n", u, down[u]);
}
}
int main()
{
int T;
scanf("%d", &T);
for (int k = 1; k <= T; k ++ )
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
idx = 0;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs_d(1, -1);
dfs_u(1, -1);
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, down[i] + up[i]);
printf("Case #%d: %d\n", k, res);
}
return 0;
}
niu
👇