【CF620E】New Year Tree

（题面来自luogu）

题意翻译

你有一棵以1为根的有根树，有n个点，每个节点初始有一个颜色c[i]。

有两种操作：

1 v c 将以v为根的子树中所有点颜色更改为c

2 v 查询以v为根的子树中的节点有多少种不同的颜色
翻译贡献者UID：28455

n、m <= 4e5，ci <= 60。

　　今天唯一听懂的一道题目，调了两个小时……因为要查询子树信息，考虑构造出dfs序之后，用线段树维护区间颜色。因为颜色只有60种，可以维护在节点上维护bitset或者一个64位整型来压缩状态，每一位上表示以该点为根的子树内是否含有这个颜色。

　　线段树内的tag是不可以累加的，每个tag都是一次直接修改，因此要在下推时特判掉空的无效标记。

代码：

  1. #include <bitset>  
  2. #include <cstdio>  
  3. #include <iostream>  
  4. #define maxn 400010  
  5. using namespace std;  
  6. template <typename T>  
  7. void read(T &x) {  
  8.     x = 0;  
  9.     int f = 1;  
  10.     char ch = getchar();  
  11.     while (!isdigit(ch)) {  
  12.         if (ch == '-')  
  13.             f = -1;  
  14.         ch = getchar();  
  15.     }  
  16.     while (isdigit(ch)) {  
  17.         x = x * 10 + (ch ^ 48);  
  18.         ch = getchar();  
  19.     }  
  20.     x *= f;  
  21.     return;  
  22. }  
  23. int n, m;  
  24. struct E {  
  25.     int to, nxt;  
  26. } edge[maxn << 1];  
  27. int head[maxn], top;  
  28. inline void insert(int u, int v) {  
  29.     edge[++top] = (E) {v, head[u]};  
  30.     head[u] = top;  
  31. }  
  32. int color[maxn], val[maxn], dfn[maxn], size[maxn], tmr;  
  33. void dfs(int u, int pre) {  
  34.     dfn[u] = ++tmr;  
  35.     size[u] = 1;  
  36.     val[tmr] = color[u];  
  37.     for (int i = head[u]; i; i = edge[i].nxt) {  
  38.         int v = edge[i].to;  
  39.         if (v != pre) {  
  40.             dfs(v, u);  
  41.             size[u] += size[v];  
  42.         }  
  43.     }  
  44. }  
  45.   
  46. namespace Segment_tree {  
  47.     #define lc (nd<<1)  
  48.     #define rc ((nd<<1)|1)  
  49.     #define mid ((l + r) >> 1)  
  50.     bitset<61> seg[maxn << 2];  
  51.     bitset<61> tag[maxn << 2];  
  52.     inline void put_tag(int nd, bitset<61> op) {  
  53.         if (op.count()) //关键，以及第一个调炸的点   
  54.             seg[nd] = op,  
  55.             tag[nd] = op;  
  56.     }  
  57.     inline void push_down(int nd) {  
  58.         put_tag(lc, tag[nd]);  
  59.         put_tag(rc, tag[nd]);  
  60.         tag[nd].reset();//第二个调炸的点：忘记清除标记   
  61.     }  
  62.     inline void update(int nd) {  
  63.         seg[nd] = seg[lc] | seg[rc];  
  64.     }  
  65.     void build(int nd, int l, int r) {  
  66.         if (l == r) {  
  67.             seg[nd].set(val[l], 1);   
  68.             return;  
  69.         }  
  70.         build(lc, l, mid);  
  71.         build(rc, mid + 1, r);  
  72.         update(nd);  
  73.     }  
  74.     void modify(int nd, int l, int r, int ql, int qr, bitset<61> op) {  
  75.         if (l >= ql && r <= qr) {  
  76.             put_tag(nd, op);  
  77.             return;  
  78.         } else if (l > qr || r < ql)  
  79.             return;  
  80.         push_down(nd);  
  81.         modify(lc, l, mid, ql, qr, op);  
  82.         modify(rc, mid + 1, r, ql, qr, op);  
  83.         update(nd);  
  84.     }  
  85.     bitset<61> query(int nd, int l, int r, int ql, int qr) {  
  86.         if (l >= ql && r <= qr)  
  87.             return seg[nd];  
  88.         if (l > qr || r < ql) {  
  89.             bitset<61> t;  
  90.             return t;  
  91.         }  
  92.         push_down(nd);  
  93.         return query(lc, l, mid, ql, qr) | query(rc, mid + 1, r, ql, qr);  
  94.     }  
  95. } using namespace Segment_tree;  
  96. int main() {  
  97.     read(n), read(m);  
  98.     for (int i = 1; i <= n; ++i)  
  99.         read(color[i]);  
  100.     int u, v, t, k;  
  101.     for (int i = 1; i < n; ++i) {  
  102.         read(u), read(v);  
  103.         insert(u, v), insert(v, u);  
  104.     }  
  105.     dfs(1, 0);  
  106.     build(1, 1, n);  
  107.     bitset<61> op;  
  108.     for (int i = 1; i <= m; ++i) {  
  109.         read(t), read(v);  
  110.         if (t == 1) {  
  111.             read(k);  
  112.             op.reset();  
  113.             op.set(k, 1);  
  114.             modify(1, 1, n, dfn[v], dfn[v] + size[v] - 1, op);  
  115.         } else {  
  116.             op = query(1, 1, n, dfn[v], dfn[v] + size[v] - 1);  
  117.             printf("%d ", op.count());  
  118.         }  
  119.     }  
  120.     return 0;  
  121. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/TY02/p/11215587.html