P2056 捉迷藏
AC_love
·
·
题解
没人写 DDP？没人写 DDP？没人写 DDP？没人写 DDP？
那么来一篇 DDP 的题解。
令开灯的点为白点，关灯的为黑点。
DDP 第一个常规套路：考虑不带修的时候怎么做树形 DP。
设 f(i, 0) 表示以 i 为根的子树中 i 到最远的黑点的距离，f(i, 1) 表示 i 点的答案。
$$f(i, 1) = \max_{x \in son_i} (f(i, 0) + f(x, 0) + 1, f(x, 1))$$
$$f(i, 0) = \max_{x \in son_i} f(x, 0) + 1$$
$i$ 为黑点时，判一下 $i$ 自己作为子树内唯一黑点的情况即可。
现在带修了，考虑怎么做。
DDP 第二个常规套路：将信息分成重儿子信息和所有轻儿子信息，考虑如何利用重儿子信息和所有轻儿子信息维护父亲信息。
令 $x$ 为 $i$ 的重儿子，$g(i, 0 / 1)$ 为 $i$ 的轻儿子的答案。
$$f(i, 0) = \max(f(x, 0) + 1, g(i, 0) + 1)$$
$$f(i, 1) = \max(f(x, 0) + g(i, 0) + 2, f(x, 1), g(i, 1))$$
DDP 第三个常规套路，把转移写成矩阵的形式：
$$\begin{bmatrix} 1 && -\inf && g(i, 0) +1 \\ g(i, 0) + 2 && 0 && g(i, 1) \\ -\inf && -\inf&& 0 \end{bmatrix} \times \begin{bmatrix} f(x, 0) \\ f(x, 1) \\ 0 \end{bmatrix} = \begin{bmatrix} f(i, 0) \\ f(i, 1) \\ 0 \end{bmatrix}$$
老生常谈的套路，对每个节点开两个 `multiset` 维护这个点上所有的 $g$，注意当这个点本身就是黑点的时候要往 $g$ 里多插一个数进去。
DDP 时注意叶子的转移矩阵需要特判。
代码细节比较多，可以看看我的代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 114;
struct matrix
{
int a[3][3];
void init() { a[0][0] = a[0][1] = a[0][2] = a[1][0] = a[1][1] = a[1][2] = a[2][0] = a[2][1] = a[2][2] = -N; }
};
matrix operator * (matrix a, matrix b)
{
matrix c;
c.init();
for(int i = 0; i < 3; i = i + 1)
for(int j = 0; j < 3; j = j + 1)
for(int k = 0; k < 3; k = k + 1)
c.a[i][j] = max(c.a[i][j], a.a[i][k] + b.a[k][j]);
return c;
}
vector <int> e[N];
struct node
{
int fa;
int dep;
int size;
int son;
int top;
int dfn;
int low;
int w;
matrix m;
multiset <int> s0, s1;
};
node d[N];
struct tree
{
int l;
int r;
matrix m;
};
int f[N][2];
void dfs1(int st, int fa, int dep)
{
d[st].w = 1;
d[st].fa = fa;
d[st].dep = dep;
d[st].size = 1;
for(auto ed : e[st])
{
if(ed == fa)
continue;
dfs1(ed, st, dep + 1);
f[st][1] = max(f[st][1], max(f[st][0] + f[ed][0] + 1, f[ed][1]));
f[st][0] = max(f[st][0], f[ed][0] + 1);
d[st].size += d[ed].size;
if(d[d[st].son].size < d[ed].size)
d[st].son = ed;
}
f[st][1] = max(f[st][1], f[st][0]);
}
void update(int x)
{
d[x].m.init();
d[x].m.a[0][0] = 1;
d[x].m.a[0][1] = -N;
if(d[x].s0.size())
d[x].m.a[0][2] = *(-- d[x].s0.end()) + 1,
d[x].m.a[1][0] = d[x].m.a[0][2] + 1;
d[x].m.a[1][1] = 0;
if(d[x].s1.size())
d[x].m.a[1][2] = *(-- d[x].s1.end());
if(d[x].s0.size() >= 2)
d[x].m.a[1][2] = max(d[x].m.a[1][2], (*(-- d[x].s0.end()) + *(-- (-- d[x].s0.end()))) + 2);
d[x].m.a[2][0] = -N;
d[x].m.a[2][1] = -N;
d[x].m.a[2][2] = 0;
}
void update_leaf(int x)
{
if(d[x].w)
d[x].m.a[0][0] = d[x].m.a[0][1] = d[x].m.a[0][2] = d[x].m.a[1][0] = d[x].m.a[1][1] = d[x].m.a[1][2] = 0;
else
d[x].m.a[0][0] = d[x].m.a[0][1] = d[x].m.a[0][2] = d[x].m.a[1][0] = d[x].m.a[1][1] = d[x].m.a[1][2] = -N;
d[x].m.a[2][0] = 0;
d[x].m.a[2][1] = 0;
d[x].m.a[2][2] = 0;
}
int cnt, nw[N];
void dfs2(int st, int top)
{
nw[++ cnt] = st;
d[st].dfn = cnt;
d[st].top = top;
d[st].low = st;
d[st].s0.insert(-1);
d[st].s1.insert(0);
if(!d[st].son)
{
update_leaf(st);
return;
}
dfs2(d[st].son, top);
d[st].low = d[d[st].son].low;
for(auto ed : e[st])
{
if(ed == d[st].fa || ed == d[st].son)
continue;
dfs2(ed, ed);
d[st].s0.insert(f[ed][0]);
d[st].s1.insert(f[ed][1]);
}
update(st);
}
struct SGT
{
tree t[N * 4];
void pushup(int p) { t[p].m = t[p << 1].m * t[p << 1 | 1].m; }
void build(int p, int l, int r)
{
t[p].l = l;
t[p].r = r;
if(l == r)
{
t[p].m = d[nw[l]].m;
return;
}
int mid = (l + r) / 2;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushup(p);
}
void change(int p, int k)
{
if(t[p].l == t[p].r)
{
t[p].m = d[nw[k]].m;
return;
}
int mid = (t[p].l + t[p].r) / 2;
if(k <= mid)
change(p << 1, k);
else
change(p << 1 | 1, k);
pushup(p);
}
matrix ask(int p, int l, int r)
{
if(l <= t[p].l && t[p].r <= r)
return t[p].m;
int mid = (t[p].l + t[p].r) / 2;
if(r <= mid)
return ask(p << 1, l, r);
if(l > mid)
return ask(p << 1 | 1, l, r);
matrix lef = ask(p << 1, l, r), rig = ask(p << 1 | 1, l, r);
return lef * rig;
}
};
SGT t;
void change(int x)
{
if(d[x].w)
{
d[x].w = 0;
if(d[x].son)
d[x].s0.erase(d[x].s0.find(-1)),
d[x].s1.erase(d[x].s1.find(0)),
update(x);
else
update_leaf(x);
}
else
{
d[x].w = 1;
if(d[x].son)
d[x].s0.insert(-1),
d[x].s1.insert(0),
update(x);
else
update_leaf(x);
}
while(x)
{
matrix bef = t.ask(1, d[d[x].top].dfn, d[d[x].low].dfn);
t.change(1, d[x].dfn);
if(d[x].top != 1)
{
matrix aft = t.ask(1, d[d[x].top].dfn, d[d[x].low].dfn);
d[d[d[x].top].fa].s0.erase(d[d[d[x].top].fa].s0.find(bef.a[0][0]));
d[d[d[x].top].fa].s1.erase(d[d[d[x].top].fa].s1.find(bef.a[1][0]));
d[d[d[x].top].fa].s0.insert(aft.a[0][0]);
d[d[d[x].top].fa].s1.insert(aft.a[1][0]);
update(d[d[x].top].fa);
}
x = d[d[x].top].fa;
}
}
int n, m;
signed main()
{
cin >> n;
for(int i = 1, x, y; i <= n - 1; i = i + 1)
{
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs1(1, 0, 1);
dfs2(1, 1);
t.build(1, 1, n);
cin >> m;
for(int i = 1; i <= m; i = i + 1)
{
char c;
cin >> c;
if(c == 'C')
{
int x;
cin >> x;
change(x);
}
else
{
int res = t.ask(1, d[1].dfn, d[d[1].low].dfn).a[1][0];
if(res >= 0)
cout << res << "\n";
else
cout << "-1\n";
}
}
return 0;
}
```