题面

\(Solution\)

通过模拟，我们会发现每次修改 \(x\)，只会改变从 \(x\) 向上一段连续的链的输出。

例如将 \(x\) 点从 \(0\) 改为 \(1，\) 那么它会影响从它向上的一段连续的链，这条链上的每一个节点的 \(1\) 儿子的个数为 \(1(\) 原来都输出 \(0\) ，改完后输出 \(1)\)

\(x\) 从 \(1\) 变 \(0\) 同理

所以我们只需要知道这条链，然后就可以树剖/\(LCT\)去维护。

这里给出 \(LCT\) 解法

记 \(val[x]\) 为 \(x\) 的儿子中 \(1\) 的个数，

那么当修改一个点 \(x\) 从 \(0\) 变 \(1\) 的时候，就成了找从根到 \(x\)的路径上最深的，val不为1的点 \(y\) ，再将 \(y\) 与 \(x\) 拉出一条链，区间修改这颗从 \(x\) 到 \(y\) 的 \(Splay (\)每个点的权值 \(+1)\) , 询问就 \(splay(1)\) ,讨论下 \(val[1]\)

\(x\) 从 \(1\) 变 \(0\) 同理

\(Source\)

#include <stdio.h>

#include <assert.h>

#include <ctype.h>

#include <set>

#include <cstring>

using namespace std;

namespace io {

    char buf[1<<21], *pos = buf, *end = buf;

    inline char getc()

    { return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; }

    inline int rint() {

        register int x = 0, f = 1; register char c;

        while (!isdigit(c = getc())) if (c == '-') f = -1;

        while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getc()));

        return x * f;

    }

    template<typename T>

        inline bool chkmin(T &x, T y) { return x > y ? (x = y, 0) : 1; }

    template<typename T>

        inline bool chkmax(T &x, T y) { return x < y ? (x = y, 0) : 1; }

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define rep(i, a, b) for (register int i = a; i <= b; ++ i)

#define dep(i, a, b) for (register int i = a; i >= b; -- i)

#define travel(i, u) for (register int i = head[u]; i; i = nxt[i])

#define mem(a, b) memset(a, b, sizeof a)

}

using io::rint;

const int N = 1.5e6 + 5;//开三倍,题目要求

int ch[N][3], n, q, fa[N];

struct LCT {

#define ls(x) (ch[x][0])

#define rs(x) (ch[x][1])

#define chk(x) (ch[fa[x]][1] == x)

    int ch[N][2], val[N], tag[N], fa[N];

    bool not1[N], not2[N];//notx[u]表示以u为根的子树中是否有权值不为x的点，没有为0, 有为1

    bool isroot(int x)

    { return ls(fa[x]) ^ x && rs(fa[x]) ^ x; }

    void add(int x, int z) {

        val[x] += z; tag[x] += z;

        if (z > 0) not2[x] = not1[x], not1[x] = 0;

        else not1[x] = not2[x], not2[x] = 0;

    }

    void pushup(int x) {

        not1[x] = not1[ls(x)] | not1[rs(x)] | (val[x] != 1);

        not2[x] = not2[ls(x)] | not2[rs(x)] | (val[x] != 2);

    }

    void pushdown(int x) {

        if (!tag[x]) return;

        if (ls(x)) add(ls(x), tag[x]);

        if (rs(x)) add(rs(x), tag[x]);

        tag[x] = 0;

    }

    void rotate(int x) {

        int y = fa[x], z = fa[y], k = chk(x), tmp = ch[x][k ^ 1];

        ch[y][k] = tmp, fa[tmp] = y;

        if (!isroot(y)) ch[z][chk(y)] = x;

        fa[x] = z;

        ch[x][k ^ 1] = y, fa[y] = x;

        pushup(y), pushup(x);

    }

    int stk[N], top;

    void splay(int x) {

        stk[top = 1] = x;

        for (int i = x; !isroot(i); i = fa[i])

            stk[++top] = fa[i];

        while (top) pushdown(stk[top--]);

        while (!isroot(x)) {

            int y = fa[x], z = fa[y];

            if (!isroot(y))

                if (chk(x) == chk(y)) rotate(y);

                else rotate(x);

            rotate(x);

        }

    }

    void access(int x) {

        for (int y = 0; x; x = fa[y = x])

            splay(x), rs(x) = y, pushup(x);

    }

    int findnot1(int x) {

        pushdown(x);

        if (!not1[x]) return 0;

        if (not1[rs(x)]) return findnot1(rs(x));

        if (val[x] != 1) return x;

        return findnot1(ls(x));

    }

    int findnot2(int x) {

        pushdown(x);

        if (!not2[x]) return 0;

        if (not2[rs(x)]) return findnot2(rs(x));

        if (val[x] != 2) return x;

        return findnot2(ls(x));

    }

} T;

void DFS(int x) {

    if (x <= n) {

        rep (i, 0, 2) {

            DFS(ch[x][i]);

            T.val[x] += (T.val[ch[x][i]] >> 1);//预处理出每个点的权值

        }

    }

} 

int main() {

#ifndef ONLINE_JUDGE

    freopen("P4332.in", "r", stdin);

    freopen("P4332.out", "w", stdout);

#endif

    n = rint();

    rep (i, 1, n) rep (j, 0, 2) {

        ch[i][j] = rint();

        fa[ch[i][j]] = T.fa[ch[i][j]] = i;

    }

    rep (i, n + 1, 3 * n + 1) {

        T.val[i] = rint(); T.val[i] ++;//很巧妙地计算权值，val存的是儿子中1的个数

    }

    DFS(1);

    q = rint();

    while (q --) {

        int x = rint();

        T.access(x);

        T.splay(x);

        if (T.val[x] > 1) {//1 - > 0 说明只有2的链才会改变

            int y = T.findnot2(T.ch[x][0]);

            T.access(fa[y]);

            T.splay(x);

            T.add(x, -1);

        } else {// 0 -> 1 说明只有1的链会改变

            int y = T.findnot1(T.ch[x][0]);

            T.access(fa[y]);

            T.splay(x);

            T.add(x, 1);

        }

        T.splay(1);

        printf("%d\n", T.val[1] > 1);

   }

}

巴特西

P4332三叉神经树

题面

\(Solution\)

\(Source\)

最新文章

热门文章