CF620E New Year Tree

· · 个人记录

jijidawang推我的那道题估计是做不出来了（不会线段树合并）
被题库卡常了（可以看到我的一页提交），于是随了道题找安慰
然后意识到之前好像见过这道题
之前不知道为什么把这东西弃了
但现在我会尽力让写这篇博客的时间和我打树剖的时间一样短（

CF620E New Year Tree

（应该再过半年再做的www）

题意简述

给定一棵树，赋予 1 ~ 60 的不同权值，要求支持子树内权值种类查询、整体修改。

题目分析

一眼切。如果值域开大点可以动态开点，但对于此题值域直接用二进制压位储存即可。
pushup 函数改为用与运算合并。
查询时调用 popcount 计算颜色个数。
记得开 long long。

Code\space Time 
#include <cstdio>
#include <cctype>
#define ls (u << 1)
#define rs (u << 1 | 1)
#define sm tree[u].sum
#define ad tree[u].add
#define lsm tree[ls].sum
#define lad tree[ls].add
#define rsm tree[rs].sum
#define rad tree[rs].add
using namespace std;

inline long long lowbit(long long x){return x & (-x);}
inline int popcount(long long x)
{
    int res = 0;
    while(x)
    {
        ++res;
        x ^= lowbit(x);
    }
    return res;
}

inline void qswap(int &a, int &b)
{
    int t = a; a = b;
    b = t; return ;
}

inline int read()
{
    int x = 0; char c;
    while(!isdigit(c = getchar()));
    do{
        x = (x << 1) + (x << 3) + (c ^ 48);
    }while(isdigit(c = getchar()));
    return x;
}

int p = 0, stk[20];
inline void write(int x)
{
    do{
        stk[++p] = x % 10;
        x /= 10;
    }while(x);
    for(register int i = p; i; --i)
        putchar(stk[i] | 48);
    putchar('\n'); p = 0;
    return ;
}

int n, m, ope, x, y, cnt = 0, tim = 0;
int head[400010], depth[400010], dfn[400010], father[400010];
int rev[400010], son[400010], sz[400010], top[400010], siz[400010];
long long bin[64];
struct edge
{
    int to;
    int next;
}e[800010];
struct node
{
    long long sum;
    long long add;
}tree[1600010];

inline void insert(int u, int v)
{
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
    return ;
}

inline void pushup(int u)
{
    sm = lsm | rsm;
    return ;
}

inline void build(int u, int l, int r)
{
    if(l == r)
    {
        sm = bin[sz[rev[l]]];
        return ;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u); return ;
}

inline void pushdown(int u)
{
    lad = rad = lsm = rsm = ad;
    ad = 0; return ;
}

inline void modify(int u, int l, int r, int lb, int rb, int val)
{
    if(lb <= l && rb >= r)
    {
        sm = ad = bin[val];
        return ;
    }
    int mid = l + r >> 1;
    if(ad) pushdown(u);
    if(lb <= mid) modify(ls, l, mid, lb, rb, val);
    if(rb > mid) modify(rs, mid + 1, r, lb, rb, val);
    pushup(u); return ;
}

inline long long query(int u, int l, int r, int lb, int rb)
{
    if(lb <= l && rb >= r) return sm;
    int mid = l + r >> 1; long long ans = 0;
    if(ad) pushdown(u);
    if(lb <= mid) ans |= query(ls, l, mid, lb, rb);
    if(rb > mid) ans |= query(rs, mid + 1, r, lb, rb);
    return ans;
}

inline void dfs1(int u, int fa)
{
    siz[u] = 1;
    for(register int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if(v == fa) continue;
        father[v] = u;
        depth[v] = depth[u] + 1;
        dfs1(v, u); siz[u] += siz[v];
        if(siz[son[u]] < siz[v]) son[u] = v;
    }
    return ;
}

inline void dfs2(int u, int tp)
{
    dfn[u] = ++tim; rev[tim] = u; top[u] = tp;
    if(son[u]) dfs2(son[u], tp);
    for(register int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if(dfn[v]) continue;
        dfs2(v, v);
    }
    return ;
}

int main()
{
    n = read(); m = read(); bin[0] = 1;
    for(register int i = 1; i <= n; ++i)
        sz[i] = read();
    for(register int i = 1; i <= 60; ++i)
        bin[i] = bin[i - 1] << 1LL;
    for(register int i = 1; i < n; ++i)
    {
        x = read(); y = read();
        insert(x, y); insert(y, x);
    }
    dfs1(1, 0); dfs2(1, 1); build(1, 1, n);
    for(register int i = 1; i <= m; ++i)
    {
        ope = read();
        if(ope == 1)
        {
            x = read(); y = read();
            modify(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, y);
        }
        else
        {
            x = read();
            write(popcount(query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1)));
        }
    }
    return 0;
}