笔记汇总
分析出它们间互相转移的地方。
设计方程将重合的部分当作偏移量提出（数组/数字维护）
下面是例题（难度排名：$P, C, K, S$）
C1
P1
本题是观察边，由于对于一条边有两类被观察到的方式，
设计状态机将所有类别表示。
/*
本题是观察边，
状态机 + 树形Dp问题
状态表示:
f(i, 0)：第i号结点没有
f(i, 1)：第i号结点有
状态计算:(j是i的子结点)
f(i, 0) = sum{f(j, 1)}
f(i, 1) = sum{min{f(j, 1), f(j, 0)}}
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1510;
int n;
int h[N], e[N], ne[N], w[N], idx;
int f[N][2], sr[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
f[u][0] = 0, f[u][1] = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
dfs(v);
f[u][0] += f[v][1];
f[u][1] += min(f[v][0], f[v][1]);
}
}
int main()
{
while (~scanf("%d", &n))
{
memset(f, 0, sizeof f);
memset(h, -1, sizeof h), idx = 0;
memset(sr, 0, sizeof sr);
int r = 0;
for (int i = 1; i <= n; i ++ )
{
int a, b, m;
scanf("%d:(%d)", &a, &m);
while (m -- )
{
scanf("%d", &b);
add(a, b);
sr[b] = 1;
}
}
while (sr[r]) r ++;
dfs(r);
printf("%d\n", min(f[r][0], f[r][1]));
}
}
P2
本题观察点，有三种被观察的类型，状态机表示。
/*
本题是观察点
状态机 + 树形Dp问题
状态表示:
f(i, 0)：第i号结点被他的父结点安排的守卫看住的方案数
f(i, 1)：第i号结点被他的子结点安排的守卫看住的方案数
f(i, 2)：第i号结点自己安排守卫看住的方案数
状态计算:(j是i的子结点)
f(i, 0) = sum{min(f(j,1), f(j,2))}
i是被他父结点看住的，那他的子结点要么自己看自己，要么被自己的子结点看住
f(i, 1) = min{w(k) - f(k, 2) + sum{min(f(j,1), f(j,2))}}
i如果是被子结点看住的，那么就要枚举他是被哪个子结点看住的所有方案，对所有方案求最小值
这里的sum不包括j==k的情况，因此需要手动额外减去
f(i, 2) = sum{min(f(j,0), f(j,1), f(j,2))} + w(u)
i是被自己看住的，那他的子结点可以被父结点看住，可以自己看自己，也可以被自己的子结点看住
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1510, INF = 1e9;
int n, root;
int h[N], e[N], ne[N], w[N], idx;
bool st[N];
int f[N][3];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
f[u][0] = 0, f[u][1] = INF, f[u][2] = w[u];
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
dfs(j);
f[u][0] += min(f[j][1], f[j][2]);
f[u][2] += min(f[j][0], min(f[j][1], f[j][2]));
}
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
f[u][1] = min(f[u][1], f[u][0] - min(f[j][1], f[j][2]) + f[j][2]);
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
int u, k, m;
scanf("%d%d%d", &u, &k, &m);
w[u] = k;
for (int j = 1; j <= m; j ++ )
{
int v;
scanf("%d", &v);
add(u, v);
st[v] = true;
}
}
for (int i = 1; i <= n; i ++ )
if (!st[i])
{
root = i;
}
dfs(root);
printf("%d", min(f[root][1], f[root][2]));
}
本题
本题有五种被观察的类型，同理表示。
不过本题可以被兄弟结点监视，状态较为复杂，
因为如果一个节点的儿子结点有加油站，则其兄弟结点会被覆盖。
据此我们设计状态，
/*
本题是观察点
状态机 + 树形Dp问题
状态表示:
f[x][0]：覆盖到x的爷爷和x整棵子树（向上2层），最少个数
f[x][1]：覆盖到x的父亲和x整棵子树（向上1层），最少个数
f[x][2]：覆盖x整棵子树（向上0层），最少个数
f[x][3]：覆盖所有x的儿子及其子树（向上-1层），最少个数
节点i的所有儿子和它们的子孙都被覆盖
f[x][4]：覆盖所有x的孙子及其子树（向上-2层），最少个数
*/
覆盖在下面讲的更清楚一些，
/*
f(u,q):在子树均被覆盖的前提下，子树最小消防局数目
q=0:u是消防局，则儿子、孙子是否是消防局，是否被其他消防局覆盖无关紧要
q=1:u非消防局，被>=1个消防局儿子覆盖
q=2:u非消防局，被>=1个消防局孙子覆盖
q=3:u非消防局，u没有被子树中消防局覆盖，但是子树中其他节点都被子树中消防局覆盖
也就是儿子都被儿子的孙子覆盖
q=4:u和所有儿子都不是消防局，也都没有被子树中消防局覆盖
*/
简洁点说：
对于已被覆盖的点可以任意选取（你当然也可以在 $u$ 不选的里面选上 $u$）
对于未被覆盖的点只能选取覆盖它们的方案。
为了简化计算，我们不重复计算哪些选取的方案（除了必选）
最后取最优即可（由 $0…4$ 是逐层涵盖的，需要满足 $ans_0 <= ans_4$）。
/*
本题是观察点
状态机 + 树形Dp问题
状态计算:(y是x的子结点)
f(x, 0) = 1+∑f[y][4]
既然当前点已经放了士兵，那么当前点的儿子节点和孙子节点全部不用放士兵
f[j][4]：覆盖所有j的孙子及其子树（向上-2层），最少个数
f(x, 1) = min(f[y][0]+∑(y!=z)f[z][3])
f(x, 2) = min(f[y][1]+∑(y!=z)f[z][2])
f(x, 3) = ∑f[y][2]
f(x, 4) = ∑f[y][3]
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 1e9;
int n;
int h[N], e[N], ne[N], w[N], idx;
int f[N][5];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs1(int u)
{
f[u][4] = 1, f[u][1] = 0, f[u][0] = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
dfs1(v);
f[u][4] += f[v][0];
f[u][1] += f[v][2];
f[u][0] += f[v][1];
}
if (h[u] == -1) f[u][2] = f[u][3] = 1;
else {
f[u][2] = f[u][3] = INF;
int cnt1 = 0, cnt2 = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
cnt1 += f[v][1];
cnt2 += f[v][2];
}
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
f[u][3] = min(f[u][3], cnt1 - f[v][1] + f[v][4]);
f[u][2] = min(f[u][2], cnt2 - f[v][2] + f[v][3]);
}
}
for (int i = 3; i >= 0; i -- )
{
f[u][i] = min(f[u][i], f[u][i+1]);
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 2; i <= n; i ++ )
{
int fa;
scanf("%d", &fa);
add(fa, i);
}
dfs1(1);
printf("%d", f[1][2]);
}
本题树形$DP$难度过大，且不太好拓展，但幸运的是这道题还有一个贪心解法。
对于一个叶子结点，它要被覆盖有：
- 它的直系兄弟有加油站
- 它的父亲有加油站
- 它自己有加油站
- 它的爷爷有加油站
由于 $4.$ 同时覆盖了 $1.2.3.$ 的结点（不是说有加油站哈）
说以选 $4.$ 是贪心最优解。
所以每次贪心取出深度最大的节点，在他的爷爷哪里放一个消防站。
记得标记完。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k = 2, t, ans;
int h[N], e[N], ne[N], w[N], idx;
int dep[N], fa[N];
struct node {
int u, d;
bool operator < (const node T) const{return d < T.d;}
};
bool st[N];
priority_queue<node> q;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs1(int u)
{
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if (!dep[v])
{
dep[v] = dep[u] + 1;
fa[v] = u;
dfs1(v);
}
}
}
int find(int x)
{
int j = 1;
while (j <= k)
{
x = fa[x];
j ++;
}
return x;
}
void dfs2(int u, int father, int step)
{
st[u] = true;
if (step == k) return;
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if (v != father) dfs2(v, u, step + 1);
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 2; i <= n; i ++ )
{
int v;
scanf("%d", &v);
add(i, v), add(v, i);
}
dep[1] = 1, fa[1] = 1;dfs1(1);
for (int i = 1; i <= n; i ++ )
{
q.push({i, dep[i]});
}
while (q.size())
{
int u = q.top().u;
q.pop();
if (st[u]) continue;
ans ++;
int v = find(u);
dfs2(v, v, 0);
}
printf("%d", ans);
}
还有一个方案，
即通过距离数组判断 $u$ 是否被覆盖到，来确定它爷爷需不需要染色。
K1
这是上面那题拓展到 $k$ 情况的问题，
我们从层数最深的结点开始寻找它的 $k$ 级祖先，
因为这涵盖了所有其它覆盖这个结点的方案，即满足了：
- 无后效性
- 子结构最优性
将驿站附近的点染色即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k, t, ans;
int h[N], e[N], ne[N], w[N], idx;
int dep[N], fa[N];
struct node {
int u, d;
bool operator < (const node T) const{return d < T.d;}
};
bool st[N];
priority_queue<node> q;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs1(int u)
{
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if (!dep[v])
{
dep[v] = dep[u] + 1;
fa[v] = u;
dfs1(v);
}
}
}
int find(int x)
{
int j = 1;
while (j <= k)
{
x = fa[x];
j ++;
}
return x;
}
void dfs2(int u, int father, int step)
{
st[u] = true;
if (step == k) return;
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if (v != father) dfs2(v, u, step + 1);
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d%d", &n, &k, &t);
for (int i = 2; i <= n; i ++ )
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
dep[1] = 1, fa[1] = 1;dfs1(1);
for (int i = 1; i <= n; i ++ )
{
q.push({i, dep[i]});
}
while (q.size())
{
int u = q.top().u;
q.pop();
if (st[u]) continue;
ans ++;
int v = find(u);
dfs2(v, v, 0);
}
printf("%d", ans);
}
// 但你依旧没有通过这道题。
这道题同样有 $DP$ 解法，之前谁说 $DP$ 不好拓展的？
当然，这里的 $DP$ 运用了贪心的思想，
考虑被控制节点 $x$，如果 $x$ 可以向上移动一，并且仍然能控制 $x$ 移动前能控制的点，就把 $x$ 向上移动，显然，这样做是不会使答案变差的。
我们不知道 $x$ 向上移动后能控制多少点，但显然，$x$有可能控制更多的点，这时把 $x$ 移动到不能移动为止，$x$ 就成为了最优答案。
回顾朴素 $DP$ 思想，即将一个点被不同点观察的情况提出，在确保满足性的前提下，求所有可能解中最优的。
而这个优化在于，我们不用考虑那么多点的观察，通过贪心确定一个点满足最优性。
所以，贪心也可能是动态规划状态的优化思想。
我们需要维护最远未被控制的点的距离和最近控制点的距离，来确定新的控制点最优可以放到哪里。
当子树中最远未被控制点 距离当前点的 距离为 $k$，则当前点设为控制点是 最优的。
如果有驿站能够到达，则将未被控制点距离设为 $-INF$，也就是没有。
如果当前点没有被覆盖，则距离为 $0$，上面的 $-INF$ 就是为了与之区分开来。
注意的是，在当前祖先往上走一步的过程中，$f$ 数组会有所变化，不能漏掉不管。
在最后，我们的根节点可能还没有被覆盖，需要特殊处理（未覆盖原因请见上文）。
对了，记得求最小值初始化最大，求最大值初始化最小。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, INF = 1e9;
int n, k, t, ans;
int h[N], e[N], ne[N], w[N], idx;
int f[N][2];
// f[0] 到最近控制驿站的距离
// f[1] 到最远的未被控制的点的距离
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int father)
{
f[u][0] = INF, f[u][1] = -INF;
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if (v == father) continue;
dfs(v, u);
f[u][0] = min(f[u][0], f[v][0] + 1);
f[u][1] = max(f[u][1], f[v][1] + 1);
}
if (f[u][0] > k) f[u][1] = max(f[u][1], 0);
if (f[u][0] + f[u][1] <= k) f[u][1] = -INF;
if (f[u][1] == k) f[u][0] = 0, f[u][1] = -INF, ans ++;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d%d", &n, &k, &t);
for (int i = 2; i <= n; i ++ )
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
dfs(1, -1);
if (f[1][1] >= 0) f[1][0] = 0, f[1][1] = -INF, ans ++;
printf("%d", ans);
}
K2
我们发现，如果确定了 $K$ 值，那么本题与上题有相似之处。
最大值最小，也可以轻易地想到二分（更小的都不满足（单调性）），
根据我们上面所讲述的计算 距离树上其它点 最远距离不超过 $K$ 的最少点数算法，
我们可以转化为计算 到关键点距离 为 $K$ 的最少点数。
并判断这个点数是否 $ >= m$。
在上一题中，我们维护最远未被控制的点的距离和最近控制点的距离，
由于本题我们只关注关键点，因此将上一题的状态表示改为最远未被控制的 关键点。
那么，更改了之后，上题的结论是否还正确？
由于，一个未被覆盖且距离控制点最远的关键点要么被它的子树内的点管理，要么被子树外的点管理。
如果子树外控制它的点距离它不超过 $K$，那么每往上一点管理的范围越广，可能覆盖的关键点越多。
同样符合贪心的性质。
我们的树并不是只有关键点，但我们只有有关键点才会去统计。
总结一下，我们的 $DP$ 有三个部分：
- 开始统计
- 计算新结点距离，状态数组转移
- 最优，计入答案，并覆盖
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10, INF = 1e9;
int n, m, k, t, ans;
int h[N], le[N], e[N], ne[N], w[N], idx;
int f[N][2];
// f[0] 到最近控制驿站的距离
// f[1] 到最远的未被控制的点的距离
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int father)
{
f[u][0] = INF, f[u][1] = -INF;
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if (v == father) continue;
dfs(v, u);
f[u][0] = min(f[u][0], f[v][0] + 1);
f[u][1] = max(f[u][1], f[v][1] + 1);
}
if (f[u][0] > k && le[u] == 1) f[u][1] = max(f[u][1], 0);
if (f[u][0] + f[u][1] <= k) f[u][1] = -INF;
if (f[u][1] == k) f[u][0] = 0, f[u][1] = -INF, ans ++;
}
int check(int mid)
{
ans = 0;
k = mid;
dfs(1, -1);
if (f[1][1] >= 0) f[1][0] = 0, f[1][1] = -INF, ans ++;
return ans;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &le[i]);
}
for (int i = 2; i <= n; i ++ )
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
int l = 0, r = n;
while (l < r) // K 的最小值（>= m） 单调递减的二分查找
{
int mid = l + r >> 1;
if (check(mid) <= m) r = mid;
else l = mid + 1;
}
printf("%d", l);
}
总结
这一类问题为了计算重复覆盖，通过不同互相涉及的阶段进行转移。
简单的树形DP题
P1
统计树的子树数量。
全集转后缀，$f[u]$ 为以 $u$ 为根的子树数量。
后缀用递推，$f[u] = \prod_{v = son(u)} (1 + f[v])$
/*
为什么在无根树上任意选一个根，它们的子树数量都相同，我以为不同根的树的形状是不同的，应该有所区别。
不少题全集转后缀时后缀顺序不用固定(本题是求联通子图数)
这句话的意思是说，
这个题的转移就是你要算u为根，那么u的子树之间互不影响，所以方案是乘起来。
我们知道乘法原理是互相独立的，所以顺序不重要。
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, mod = 1000000007;
typedef unsigned long long LL;
int n;
LL f[N], ans;
int h[N], e[N], ne[N], w[N], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs1(int u, int fa)
{
f[u] = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if (v == fa) continue;
dfs1(v, u);
f[u] = (f[u] * (1 + f[v])) % mod;
}
ans = (ans + f[u]) % mod;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 1; i < n; i ++ )
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
dfs1(1, -1);
printf("%lld", ans);
}
P2
本题背包处，有一个偏移量，我们应该将其剔除，
以避免重复计算偏移量造成的错误。
P3
板子题，有边权的最小深度和换根$DP$问题。
God helps those whose help themselves!