[CF877E] Danil and a Part-time Job

[CF877E] Danil and a Part-time Job - DFS序,线段树

Description

有一棵 (n) 个点的树，根结点为 (1) 号点，每个点的权值都是 (1) 或 (0)，操作两种，询问一个点 (x) 的子树里有多少个 (1)，将一个点 (x) 的子树中所有节点取反

Solution

DFS 序转化为序列问题后线段树维护每个区间 1 的个数即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1000005;

vector<int> g[N];
int dfn[N], fin[N], ind;

void dfs(int p, int from)
{
    dfn[p] = ++ind;
    for (int q : g[p])
    {
        if (q == from)
            continue;
        dfs(q, p);
    }
    fin[p] = ind;
}

// segtree

int a[N], tag[N];

void pushup(int p)
{
    a[p] = a[p * 2] + a[p * 2 + 1];
}

void pushdown(int p, int l, int r)
{
    if (tag[p])
    {
        tag[p] = 0;
        a[p * 2] = ((l + r) / 2 - l + 1) - a[p * 2];
        tag[p * 2] ^= 1;
        a[p * 2 + 1] = (r - (l + r) / 2) - a[p * 2 + 1];
        tag[p * 2 + 1] ^= 1;
    }
}

void build(int p, int l, int r, int *src)
{
    if (l == r)
    {
        a[p] = src[l];
    }
    else
    {
        build(p * 2, l, (l + r) / 2, src);
        build(p * 2 + 1, (l + r) / 2 + 1, r, src);
        pushup(p);
    }
}

void modify(int p, int l, int r, int ql, int qr)
{
    if (l > qr || r < ql)
        return;
    if (l >= ql && r <= qr)
    {
        a[p] = r - l + 1 - a[p];
        tag[p] ^= 1;
    }
    else
    {
        pushdown(p, l, r);
        modify(p * 2, l, (l + r) / 2, ql, qr);
        modify(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
        pushup(p);
    }
}

int query(int p, int l, int r, int ql, int qr)
{
    if (l > qr || r < ql)
        return 0;
    if (l >= ql && r <= qr)
        return a[p];
    pushdown(p, l, r);
    return query(p * 2, l, (l + r) / 2, ql, qr) + query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
}

int val[N], seq[N];
int n, m;

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        int fa;
        cin >> fa;
        g[fa].push_back(i);
    }

    for (int i = 1; i <= n; i++)
    {
        cin >> val[i];
    }

    dfs(1, 0);

    for (int i = 1; i <= n; i++)
    {
        seq[dfn[i]] = val[i];
    }

    build(1, 1, n, seq);

    cin >> m;

    for (int i = 1; i <= m; i++)
    {
        string op;
        int x;
        cin >> op >> x;
        if (op == "get")
        {
            cout << query(1, 1, n, dfn[x], fin[x]) << endl;
        }
        else
        {
            modify(1, 1, n, dfn[x], fin[x]);
        }
    }
}