『树形DP·换根』The Crazy Tree(毒瘤)

题目描述

给定一棵 $n$ 个结点的树，结点编号为 $1?n$，$i$号结点的权重记为 $wi$（每个点的权值各不相同）。我们定义一个“疯子树”为： 1. 是一个联通子图。 2. 我们将子图内的点按照权重从小到大排序后序列为 $b1,b2,\dots ,bm$，对于任意的$i(i<m)$,$bi$到$bi+1$。最短路径（不含$bi$和$bi+1$）上的结点的权值都小于等于$w_{bi}$。输出包含结点最多的“疯子树”的结点数。

题解

首先，树中两点的路径唯一，不需要考虑最短路。

其次，我们考虑一下疯子书这个树有什么特殊的性质：

• 我们发现，每一棵疯子树中任意两点间的权值都小于这两个点。如果是一条链的话，必然是连续的不断并且一次递减；如果是一棵树的话，这棵树和每一个子树都满足根节点为最小点的树一定是疯子树。

显然，以不同的节点为根会产生不同的答案，由于题目中说的是无根树我们可以采用换根的方法来进行处理。

我们设$g[x]$表示以$x$为根的子树中，节点最多的疯子树。根据疯子树的性质，我们可以得到：
$$g[x]=1+\sum _{y\in son(x),w_y\ge w_x}g[y]$$
同时，我们第二次进行操作时，设$f[i]$表示以$i$为根最后的总答案。同样可以得到：
$$f[x]=g[x]+f[fa](when{w}_x\ge w_{fa})$$
此时由于满足条件$w_x\ge w_{fa}$,$g[x]$中不可能包含父节点$fa$。

时间复杂度：$O(N)$.

代码如下：

#include <bits/stdc++.h> using namespace std;
const int N = 200010;inline int read(void)
{
    int s = 0, w = 1; char c = getchar();while (c < '0' || c > '9') c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return s * w;
} int n;
int f[N], g[N], w[N];
vector <int> a[N];void dfs(int x,int fa)
{
    g[x] = 1;for (int i=0;i<a[x].size();++i){
    int y = a[x][i];if (y == fa) continue;dfs(y,x);if (w[y] >= w[x]) g[x] += g[y];}f[x] = g[x];return;
}void dp(int x,int fa)
{
    for (int i=0;i<a[x].size();++i){
    int y = a[x][i];if (y == fa) continue;if (w[y] <= w[x]) f[y] += f[x];dp(y,x);}return;
}int main(void)
{
    freopen("crazy.in","r",stdin);freopen("crazy.out","w",stdout);while (cin >> n){
    for (int i=1;i<=n;++i) w[i] = read();for (int i=0;i<N;++i) a[i].clear();for (int i=1;i<n;++i){
    int x = read(), y = read();a[x].push_back(y);a[y].push_back(x);}dfs(1,0), dp(1,0);int ans = 0;for (int i=1;i<=n;++i) ans = max(ans,f[i]);cout << ans << endl;}return 0;
}

因此我们便可以放心DP喽~