題目鏈接：[點擊打開鏈接](http://codeforces.com/contest/620/problem/E) 題意：給你一棵樹，編號1~n，告訴你根結點是1。 每次有兩個操作： 1，將以v為根的子樹的結點全部染成顏色c 2，問以v為根的紫書的結點的顏色種類。 思路：如果這是一條線段的話， 那么這就是線段樹的區間更新問題，而現在是一棵樹。 因為告訴了根結點是1， 那么這棵樹的任意一個結點的子樹就是確定的， 所以我們可以用DFS的先序遍歷，將所有結點重新編號，因為先序遍歷的話， 任意一個結點和其子樹的編號就是一條連續的線段了，在這其中維護每個結點的新編號， 和這個結點的子樹中的最大編號即可。 然后就是線段樹區間更新了， 由于顏色數最大60， 用long long通過位運算的 | 操作就行了， 注意對1左移的時候應該先將1轉成long long再進行操作。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 400000 + 10; int T,n,m,u,v,id[maxn],a[maxn],cnt,last[maxn],b[maxn],setv[maxn<<2]; bool vis[maxn]; ll sum[maxn<<2]; vector<int> g[maxn]; void dfs(int root) { id[root] = ++cnt; vis[root] = true; int len = g[root].size(); for(int i=0;i<len;i++) { int v = g[root][i]; if(!vis[v]) { dfs(v); } } last[root] = cnt; } void PushUp(int o) { sum[o] = sum[o<<1] | sum[o<<1|1]; } void pushdown(int l, int r, int o) { if(setv[o]) { setv[o<<1] = setv[o<<1|1] = setv[o]; sum[o<<1] = sum[o<<1|1] = (1LL<<setv[o]); setv[o] = 0; } } void build(int l, int r, int o) { int m = (l + r) >> 1; setv[o] = 0; if(l == r) { sum[o] = 1LL<<b[++cnt]; return ; } build(l, m, o<<1); build(m+1, r, o<<1|1); PushUp(o); } void update(int L, int R, int v, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { setv[o] = v; sum[o] = (1LL << v); return ; } pushdown(l, r, o); if(L <= m) update(L, R, v, l, m, o<<1); if(m < R) update(L, R, v, m+1, r, o<<1|1); PushUp(o); } ll query(int L, int R, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { return sum[o]; } pushdown(l, r, o); ll ans = 0; if(L <= m) ans |= query(L, R, l, m, o<<1); if(m < R) ans |= query(L, R, m+1, r, o<<1|1); PushUp(o); return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); g[u].clear(); } for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } memset(vis, 0, sizeof(vis)); cnt = 0; dfs(1); for(int i=1;i<=n;i++) { b[id[i]] = a[i]; } cnt = 0; build(1, n, 1); int res, v, c; while(m--) { scanf("%d",&res); if(res == 1) { scanf("%d%d",&v,&c); update(id[v], last[v], c, 1, n, 1); } else { scanf("%d",&v); ll ans = query(id[v], last[v], 1, n, 1); int cc = 0; for(int i=1;i<=61;i++) { if(ans & (1LL<<i)) cc++; } printf("%d\n",cc); } } return 0; } ~~~