codeforces 620E. New Year Tree dfs序+线段树+bitset

题目链接

给一棵树， 每个节点有颜色， 两种操作， 一种是将一个节点的子树全都染色成c， 一种是查询一个节点的子树有多少个不同的颜色， c<=60.

每个节点一个bitset维护就可以。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

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

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

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

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

const int maxn = 4e5+;

struct node

{

    int to, nextt;

}e[maxn*];

int lazy[maxn<<], a[maxn], in[maxn], out[maxn], head[maxn*], num, clock;

bitset <> s[maxn<<];

void add(int u, int v) {

    e[num].to = v, e[num].nextt = head[u], head[u] = num++;

}

void pushUp(int rt) {

    s[rt] = s[rt<<]|s[rt<<|];

}

void pushDown(int rt) {

    if(lazy[rt]) {

        lazy[rt<<] = lazy[rt<<|] = lazy[rt];

        s[rt<<].reset();

        s[rt<<|].reset();

        s[rt<<][lazy[rt]] = s[rt<<|][lazy[rt]] = ;

        lazy[rt] = ;

        return ;

    }

}

void update(int val, int L, int R, int l, int r, int rt) {

    if(L<=l&&R>=r) {

        s[rt].reset();

        s[rt][val] = ;

        lazy[rt] = val;

        return ;

    }

    pushDown(rt);

    int m = l+r>>;

    if(L<=m)

        update(val, L, R, lson);

    if(R>m)

        update(val, L, R, rson);

    pushUp(rt);

}

void dfs(int u, int fa) {

    in[u] = ++clock;

    for(int i = head[u]; ~i; i = e[i].nextt) {

        int v = e[i].to;

        if(v == fa)

            continue;

        dfs(v, u);

    }

    out[u] = clock;

}

bitset<> query(int L, int R, int l, int r, int rt) {

    if(L<=l&&R>=r) {

        return s[rt];

    }

    pushDown(rt);

    bitset<> tmp;

    tmp.reset();

    int m = l+r>>;

    if(L<=m)

        tmp |= query(L, R, lson);

    if(R>m)

        tmp |= query(L, R, rson);

    return tmp;

}

int main()

{

    int q, n, m, x, y;

    int ch;

    memset(head, -, sizeof(head));

    cin>>n>>m;

    for(int i = ; i<=n; i++)

        scanf("%d", &a[i]);

    for(int i = ; i<n; i++) {

        scanf("%d%d", &x, &y);

        add(x, y);

        add(y, x);

    }

    dfs(, );

    for(int i = ; i<=n; i++) {

        update(a[i], in[i], in[i], , n, );

    }

    while(m--) {

        scanf("%d%d", &ch, &x);

        if(ch == )

            printf("%d\n", query(in[x], out[x], , n, ).count());

        else {

            int z;

            scanf("%d", &z);

            update(z, in[x], out[x], , n, );

        }

    }

    return ;

}