专栏文章

P2056 捉迷藏

AAC_loveRealNewbie
P2056题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miprapc6
此快照首次捕获于
2025/12/03 16:39
3 个月前
此快照最后确认于
2025/12/03 16:39
3 个月前
查看原文
没人写 DDP？没人写 DDP？没人写 DDP？没人写 DDP？
那么来一篇 DDP 的题解。
令开灯的点为白点，关灯的为黑点。
DDP 第一个常规套路：考虑不带修的时候怎么做树形 DP。
设 f(i,0)f(i, 0) 表示以 ii 为根的子树中 ii 到最远的黑点的距离，f(i,1)f(i, 1) 表示 ii 点的答案。
ii 为白点时，有转移：
f(i,1)=max⁡x∈soni(f(i,0)+f(x,0)+1,f(x,1))f(i, 1) = \max_{x \in son_i} (f(i, 0) + f(x, 0) + 1, f(x, 1))
f(i,0)=max⁡x∈sonif(x,0)+1f(i, 0) = \max_{x \in son_i} f(x, 0) + 1
ii 为黑点时，判一下 ii 自己作为子树内唯一黑点的情况即可。
现在带修了，考虑怎么做。
DDP 第二个常规套路：将信息分成重儿子信息和所有轻儿子信息，考虑如何利用重儿子信息和所有轻儿子信息维护父亲信息。
令 xx 为 ii 的重儿子，g(i,0/1)g(i, 0 / 1) 为 ii 的轻儿子的答案。
f(i,0)=max⁡(f(x,0)+1,g(i,0)+1)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))f(i, 1) = \max(f(x, 0) + g(i, 0) + 2, f(x, 1), g(i, 1))
DDP 第三个常规套路，把转移写成矩阵的形式：
[1−inf⁡g(i,0)+1g(i,0)+20g(i,1)−inf⁡−inf⁡0]×[f(x,0)f(x,1)0]=[f(i,0)f(i,1)0]\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 维护这个点上所有的 gg，注意当这个点本身就是黑点的时候要往 gg 里多插一个数进去。
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...