DFS序
总结：
1、树转化为线性：将树通过dfs转化为线性结构，这就是dfs序，和树链剖分有点相似
2、普通树转化为线段树：记录每个节点构成的树（子树）的起点和终点，起点是自己，这样每个点就构成了一个区间，然后对区间的操作就和线段树和树状数组一样了。
3、DFS序主要用来做子树的更新，因为DFS序中子树都是连续的。时间复杂度看树的储存结构，O（1）。
4、树的储存可以用图来存储，图的数组模拟邻接矩阵：小兵应该先武装好自己，然后再加入队伍，队长负责周转（管最前面一个）。
详解：
给定一棵n个节点的树，m次查询，每次查询需要求出某个节点深度为h的所有子节点。
对于这个问题如果试图去对每个节点保存所有深度的子节点，在数据大的时候内存会吃不消；或者每次查询的时候去遍历一遍，当数据大的时候，时间效率会非常低。
此时如果使用dfs序维护树结构就可以轻松地解决这个问题。
作为预处理，首先将将树的所有节点按深度保存起来，每个深度的所有节点用一个线性结构保存，每个深度的节点相对顺序要和前序遍历一致。
然后从树的根节点进行dfs，对于每个节点记录两个信息，一个是dfs进入该节点的时间戳in[id]，另一个是dfs离开该节点的时间戳out[id]。
最后对于每次查询，求节点v在深度h的所有子节点，只需将深度为h并且dfs进入时间戳在in[v]和out[v]之间的所有节点都求出来即可，由于对于每个深度的所有节点，相对顺序和前序遍历的顺序以致，那么他们的dfs进入时间戳也是递增的，于是可以通过二分搜索求解。
分析
Step 1：
如下图，可以看到，由于普通的树并不具有区间的性质，所以在考虑使用线段树作为解题思路时，需要对给给定的数据进行转化，首先对这棵树进行一次dfs遍历，记录dfs序下每个点访问起始时间与结束时间，记录起始时间是前序遍历，结束时间是后序遍历，同时对这课树进行重标号。
Step 2：
如下图，DFS之后，那么树的每个节点就具有了区间的性质。
那么此时，每个节点对应了一个区间，而且可以看到，每个节点对应的区间正好“管辖”了它子树所有节点的区间，那么对点或子树的操作就转化为了对区间的操作。
【PS: 如果对树的遍历看不懂的话，不妨待会对照代码一步一步调试，或者在纸上模拟过程~】
Step 3：
这个时候，每次对节点进行更新或者查询，就是线段树和树状数组最基本的实现了…
树是一种非线性结构，一般而言，我们总是想办法将其转化为线性结构，将树上操作包括子树操作、路径操作等转化为数组上的区间操作，从而在一个较为理想的复杂度内加以解决。将树“拍平”的方法有很多，例如欧拉序、HLD等。实际上欧拉序也是在DFS过程中得到的。不过通常而言，我们所说的DFS序是指：每个节点进出栈的时间序列。
考虑上图中树的DFS序，应为
其中，每个节点均会出现2次，第一次是进入DFS的时刻，第二次是离开DFS的时刻。分别称之为In与Out。在区间操作中，如果某个节点出现了2次，则该节点将被“抵消”。所以通常会将Out时刻对应的点设置为负数。
树的DFS序列有几个有用的性质：
- 任意子树是连续的。例如子树BEFK，在序列中对应BEEFKKFB；子树CGHI，在序列中对应连续区间CGGHHIIC。
- 任意点对(a,b)之间的路径，可分为2种情况，首先令lca是a、b的最近公共祖先：
- 若lca是a、b之一，则a、b之间的In时刻的区间或者Out时刻区间就是其路径。例如AK之间的路径就对应区间ABEEFK，或者KFBCGGHHIICA。
- 若lca另有其人，则a、b之间的路径为In[a]、Out[b]之间的区间或者In[b]、Out[a]之间的区间。另外，还需额外加上lca！！！考虑EK路径，对应为EFK再加上B。考虑EH之间的路径，对应为EFKKFBCGGH再加上A。
利用这些性质，可以利用DFS序列完成子树操作和路径操作，同时也有可能将莫队算法应用到树上从而得到树上莫队。
代码：
dfs序是处理树上问题很重要的一个武器，主要能够解决对于一个点，它的子树上的一些信息的维护。
就比如那天百度之星round1A的1003题，就是dfs序+线段树维护每个点到0点的距离，然后对于每个点的更新，只需要更新它和它的子树上的点到0点的距离，查询的话就是它的子树上的最大值即可
我的dfs序开的空间就是n，因为只在入的地方时间戳++，出来的地方时间戳不变，线段树的每个节点应该是时间戳
1 void dfs(int u,int fa){ 2 p1[u]=++ti; 3 dfsnum[ti]=u; 4 for(int i=head[u];i!=-1;i=edge[i].next){ 5 int v=edge[i].v; 6 if(v==fa) continue; 7 dfs(v,u); 8 } 9 p2[u]=ti;//时间戳不变，空间为O(n) 10 }
例题：
BZOJ4034需要在树上完成3类操作，单点更新，子树更新，以及根到指定节点的路径查询。利用性质1以及性质2.1即可完成，连LCA都无需求出。对整个DFS序列使用线段树进行维护，注意到整个序列实际上有正有负，因此额外用一个域来表示正数的个数。
4034: [HAOI2015]树上操作
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 6323 Solved: 2094
[Submit][Status][Discuss]
Description
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
Input
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1
行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中
第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
Output
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
Sample Input
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
Sample Output
6
9
13
9
13
HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
Source
1 #include <cstdio> 2 #include <climits> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 7 int const SIZE = 100100; 8 typedef long long weight_t; 9 10 struct edge_t{//边 11 int to; 12 int next; 13 }Edge[SIZE<<1];//双向的 所以*2 14 int Vertex[SIZE]; 15 int ECnt; 16 weight_t W[SIZE]; 17 18 //数组模拟邻接矩阵：顶点记录的是下一个点，顶点负责转运 19 inline void mkEdge(int a,int b){//造a-b这条边 20 //先把节点的信息补充好，再建立联系 21 //先武装好自己，然后再图报效 22 //每个队的长官记录每个队节点的分配信息 23 Edge[ECnt].to = b; 24 Edge[ECnt].next = Vertex[a]; 25 Vertex[a] = ECnt++; 26 27 Edge[ECnt].to = a; 28 Edge[ECnt].next = Vertex[b]; 29 Vertex[b] = ECnt++; 30 } 31 32 int InIdx[SIZE],OutIdx[SIZE]; 33 int InOut[SIZE<<1]; 34 int NewIdx[SIZE<<1]; 35 int NCnt; 36 37 void dfs(int node,int parent){ 38 NewIdx[NCnt] = node; 39 InOut[NCnt] = 1; 40 InIdx[node] = NCnt++; 41 for(int next=Vertex[node];next;next=Edge[next].next){ 42 int son = Edge[next].to; 43 if ( son != parent ) dfs(son,node); 44 } 45 NewIdx[NCnt] = node; 46 InOut[NCnt] = -1; 47 OutIdx[node] = NCnt++; 48 } 49 50 int N; 51 weight_t StSum[SIZE<<3]; 52 weight_t Lazy[SIZE<<3]; 53 int Flag[SIZE<<3];//The count of the positive number in the range 54 55 inline int lson(int x){return x<<1;} 56 inline int rson(int x){return lson(x)|1;} 57 58 inline void _pushUp(int t){ 59 StSum[t] = StSum[lson(t)] + StSum[rson(t)]; 60 Flag[t] = Flag[lson(t)] + Flag[rson(t)]; 61 } 62 63 inline void _pushDown(int t){ 64 if ( 0LL == Lazy[t] ) return; 65 66 weight_t& x = Lazy[t]; 67 68 int son = lson(t); 69 StSum[son] += Flag[son] * x; 70 Lazy[son] += x; 71 72 son = rson(t); 73 StSum[son] += Flag[son] * x; 74 Lazy[son] += x; 75 76 x = 0LL; 77 } 78 79 void build(int t,int s,int e){ 80 Lazy[t] = 0LL; 81 if ( s == e ){ 82 StSum[t] = InOut[s] * W[NewIdx[s]]; 83 Flag[t] = InOut[s]; 84 return; 85 } 86 87 int m = ( s + e ) >> 1; 88 build(lson(t),s,m); 89 build(rson(t),m+1,e); 90 _pushUp(t); 91 } 92 93 void modify(int t,int s,int e,int a,int b,weight_t delta){ 94 if ( a <= s && e <= b ){ 95 StSum[t] += Flag[t] * delta; 96 Lazy[t] += delta; 97 return; 98 } 99 100 _pushDown(t); 101 int m = ( s + e ) >> 1; 102 if ( a <= m ) modify(lson(t),s,m,a,b,delta); 103 if ( m < b ) modify(rson(t),m+1,e,a,b,delta); 104 _pushUp(t); 105 } 106 107 weight_t query(int t,int s,int e,int a,int b){ 108 if ( a <= s && e <= b ){ 109 return StSum[t]; 110 } 111 112 _pushDown(t); 113 114 weight_t ret = 0LL; 115 int m = ( s + e ) >> 1; 116 if ( a <= m ) ret += query(lson(t),s,m,a,b); 117 if ( m < b ) ret += query(rson(t),m+1,e,a,b); 118 return ret; 119 } 120 121 inline weight_t query(int x){ 122 return query(1,1,N<<1,1,InIdx[x]); 123 } 124 125 inline void modify(int x,weight_t delta){ 126 modify(1,1,N<<1,InIdx[x],InIdx[x],delta); 127 modify(1,1,N<<1,OutIdx[x],OutIdx[x],delta); 128 } 129 130 inline void modifySubtree(int x,weight_t delta){ 131 modify(1,1,N<<1,InIdx[x],OutIdx[x],delta); 132 } 133 134 //这里树的储存方式用的是图里面的数组仿邻接矩阵 135 inline void initTree(int n){ 136 ECnt = NCnt = 1; 137 //vertex是顶点，这就是存储边的方式 138 fill(Vertex,Vertex+n+1,0); 139 } 140 141 int M; 142 bool read(){ 143 if ( EOF == scanf("%d%d",&N,&M) ) return false; 144 145 initTree(N); 146 for(int i=1;i<=N;++i)scanf("%lld",W+i);//读权值 147 148 int a,b; 149 for(int i=1;i<N;++i){ 150 scanf("%d%d",&a,&b);//读每一条边 151 mkEdge(a,b);//造边 152 } 153 cout<<"Edge[i].to"<<" "<<"Edge[i].next"<<endl; 154 for(int i=0;i<=20;i++){ 155 cout<<Edge[i].to<<" "<<Edge[i].next<<endl; 156 } 157 dfs(1,0); 158 build(1,1,N<<1); 159 return true; 160 } 161 162 void proc(){ 163 int cmd,x; 164 weight_t a; 165 while(M--){ 166 scanf("%d%d",&cmd,&x); 167 switch(cmd){ 168 case 1:scanf("%lld",&a);modify(x,a);break; 169 case 2:scanf("%lld",&a);modifySubtree(x,a);break; 170 case 3:printf("%lld ",query(x));break; 171 } 172 } 173 } 174 int main(){ 175 freopen("in.txt","r",stdin); 176 while( read() ) proc(); 177 return 0; 178 }
HDU 3887
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3887
问你对于每个节点，它的子树上标号比它小的点有多少个
子树的问题，dfs序可以很轻松的解决，因为点在它的子树上，所以在线段树中，必定在它的两个时间戳的区间之间，所以我们只需要从小到大考虑，它的区间里有多少个点已经放了，然后再把它放进去。很容易的解决了
代码：
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <sstream> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker, "/STACK:102400000,102400000") 16 17 using namespace std; 18 #define MAX 500005 19 #define MAXN 6005 20 #define maxnode 15 21 #define sigma_size 30 22 #define lson l,m,rt<<1 23 #define rson m+1,r,rt<<1|1 24 #define lrt rt<<1 25 #define rrt rt<<1|1 26 #define middle int m=(r+l)>>1 27 #define LL long long 28 #define ull unsigned long long 29 #define mem(x,v) memset(x,v,sizeof(x)) 30 #define lowbit(x) (x&-x) 31 #define pii pair<int,int> 32 #define bits(a) __builtin_popcount(a) 33 #define mk make_pair 34 #define limit 10000 35 36 //const int prime = 999983; 37 const int INF = 0x3f3f3f3f; 38 const LL INFF = 0x3f3f; 39 const double pi = acos(-1.0); 40 //const double inf = 1e18; 41 const double eps = 1e-8; 42 const LL mod = 1e9+7; 43 const ull mx = 133333331; 44 45 /*****************************************************/ 46 inline void RI(int &x) { 47 char c; 48 while((c=getchar())<'0' || c>'9'); 49 x=c-'0'; 50 while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0'; 51 } 52 /*****************************************************/ 53 54 struct Edge{ 55 int v,next; 56 }edge[MAX*2]; 57 int head[MAX]; 58 int tot; 59 int p1[MAX]; 60 int p2[MAX]; 61 int ti; 62 int sum[MAX<<2]; 63 64 void init(){ 65 mem(head,-1); 66 tot=0;ti=0; 67 } 68 69 void add_edge(int a,int b){ 70 edge[tot]=(Edge){b,head[a]}; 71 head[a]=tot++; 72 } 73 74 void dfs(int u,int fa){ 75 p1[u]=++ti; 76 for(int i=head[u];i!=-1;i=edge[i].next){ 77 int v=edge[i].v; 78 if(v==fa) continue; 79 dfs(v,u); 80 } 81 p2[u]=ti; 82 } 83 84 void build(int l,int r,int rt){ 85 sum[rt]=0; 86 if(l==r) return; 87 middle; 88 build(lson); 89 build(rson); 90 } 91 92 void pushup(int rt){ 93 sum[rt]=sum[lrt]+sum[rrt]; 94 } 95 96 void update(int l,int r,int rt,int pos,int d){ 97 if(l==r){ 98 sum[rt]+=d; 99 return; 100 } 101 middle; 102 if(pos<=m) update(lson,pos,d); 103 else update(rson,pos,d); 104 pushup(rt); 105 } 106 107 int query(int l,int r,int rt,int L,int R){ 108 if(L<=l&&r<=R) return sum[rt]; 109 middle; 110 int ret=0; 111 if(L<=m) ret+=query(lson,L,R); 112 if(R>m) ret+=query(rson,L,R); 113 return ret; 114 } 115 116 int main(){ 117 int n,p; 118 while(cin>>n>>p&&n){ 119 init(); 120 for(int i=1;i<n;i++){ 121 int a,b; 122 scanf("%d%d",&a,&b); 123 add_edge(a,b); 124 add_edge(b,a); 125 } 126 dfs(p,-1); 127 build(1,n,1); 128 for(int i=1;i<=n;i++){ 129 printf("%d",query(1,n,1,p1[i],p2[i])); 130 if(i==n) printf(" "); 131 else printf(" "); 132 update(1,n,1,p1[i],1); 133 } 134 } 135 return 0; 136 }
poj 3321
题目传送门：http://poj.org/problem?id=3321
这题是一开始告诉你树上每个节点都有1个苹果，然后你对一个节点操作，如果有苹果，就拿走，没苹果，就放上，然后询问你以x为根的子树上有多少个苹果。
dfs序水题，代码：
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <sstream> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker, "/STACK:102400000,102400000") 16 17 using namespace std; 18 #define MAX 500005 19 #define MAXN 6005 20 #define maxnode 15 21 #define sigma_size 30 22 #define lson l,m,rt<<1 23 #define rson m+1,r,rt<<1|1 24 #define lrt rt<<1 25 #define rrt rt<<1|1 26 #define middle int m=(r+l)>>1 27 #define LL long long 28 #define ull unsigned long long 29 #define mem(x,v) memset(x,v,sizeof(x)) 30 #define lowbit(x) (x&-x) 31 #define pii pair<int,int> 32 #define bits(a) __builtin_popcount(a) 33 #define mk make_pair 34 #define limit 10000 35 36 //const int prime = 999983; 37 const int INF = 0x3f3f3f3f; 38 const LL INFF = 0x3f3f; 39 const double pi = acos(-1.0); 40 //const double inf = 1e18; 41 const double eps = 1e-8; 42 const LL mod = 1e9+7; 43 const ull mx = 133333331; 44 45 /*****************************************************/ 46 inline void RI(int &x) { 47 char c; 48 while((c=getchar())<'0' || c>'9'); 49 x=c-'0'; 50 while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0'; 51 } 52 /*****************************************************/ 53 54 struct Edge{ 55 int v,next; 56 }edge[MAX*2]; 57 int head[MAX]; 58 int tot; 59 int p1[MAX]; 60 int p2[MAX]; 61 int ti; 62 int sum[MAX<<2]; 63 64 void init(){ 65 mem(head,-1); 66 tot=0;ti=0; 67 } 68 69 void add_edge(int a,int b){ 70 edge[tot]=(Edge){b,head[a]}; 71 head[a]=tot++; 72 } 73 74 void dfs(int u,int fa){ 75 p1[u]=++ti; 76 for(int i=head[u];i!=-1;i=edge[i].next){ 77 int v=edge[i].v; 78 if(v==fa) continue; 79 dfs(v,u); 80 } 81 p2[u]=ti; 82 } 83 84 void pushup(int rt){ 85 sum[rt]=sum[lrt]+sum[rrt]; 86 } 87 88 void build(int l,int r,int rt){ 89 if(l==r){ 90 sum[rt]=1; 91 return; 92 } 93 middle; 94 build(lson); 95 build(rson); 96 pushup(rt); 97 } 98 99 void update(int l,int r,int rt,int pos){ 100 if(l==r){ 101 sum[rt]=sum[rt]^1; 102 return; 103 } 104 middle; 105 if(pos<=m) update(lson,pos); 106 else update(rson,pos); 107 pushup(rt); 108 } 109 110 int query(int l,int r,int rt,int L,int R){ 111 if(L<=l&&r<=R) return sum[rt]; 112 middle; 113 int ret=0; 114 if(L<=m) ret+=query(lson,L,R); 115 if(R>m) ret+=query(rson,L,R); 116 return ret; 117 } 118 119 int main(){ 120 int n; 121 cin>>n; 122 init(); 123 for(int i=1;i<n;i++){ 124 int a,b; 125 scanf("%d%d",&a,&b); 126 add_edge(a,b); 127 add_edge(b,a); 128 } 129 dfs(1,-1); 130 build(1,n,1); 131 int m; 132 scanf("%d",&m); 133 while(m--){ 134 char op; 135 int a; 136 getchar(); 137 scanf("%c%d",&op,&a); 138 if(op=='Q') printf("%d ",query(1,n,1,p1[a],p2[a])); 139 else update(1,n,1,p1[a]); 140 } 141 return 0; 142 }
CodeForces 620E
题目传送门：http://codeforces.com/problemset/problem/620/E
给你一棵树，每个节点都有颜色，然后问你子树上有多少种不同的颜色
考虑到颜色一共只有60种，所以可以直接二进制记录，每个节点记录这个节点的颜色，然后区间直接左右子树或起来，然后对x为根的子树都变成c颜色，区间赋值，需要pushdown，pushup。
有个坑点就是需要记录每个时间戳是哪个点，然后在build线段树的时候，sum[rt]=c[dfsnum[l]]，这个坑点我错了好久，因为线段树的节点的下标应该是时间戳。GG，仍需努力
代码：
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <sstream> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker, "/STACK:102400000,102400000") 16 17 using namespace std; 18 #define MAX 400005 19 #define MAXN 6005 20 #define maxnode 15 21 #define sigma_size 30 22 #define lson l,m,rt<<1 23 #define rson m+1,r,rt<<1|1 24 #define lrt rt<<1 25 #define rrt rt<<1|1 26 #define middle int m=(r+l)>>1 27 #define LL long long 28 #define ull unsigned long long 29 #define mem(x,v) memset(x,v,sizeof(x)) 30 #define lowbit(x) (x&-x) 31 #define pii pair<int,int> 32 #define bits(a) __builtin_popcount(a) 33 #define mk make_pair 34 #define limit 10000 35 36 //const int prime = 999983; 37 const int INF = 0x3f3f3f3f; 38 const LL INFF = 0x3f3f; 39 const double pi = acos(-1.0); 40 //const double inf = 1e18; 41 const double eps = 1e-8; 42 const LL mod = 1e9+7; 43 const ull mx = 133333331; 44 45 /*****************************************************/ 46 inline void RI(int &x) { 47 char c; 48 while((c=getchar())<'0' || c>'9'); 49 x=c-'0'; 50 while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0'; 51 } 52 /*****************************************************/ 53 54 struct Edge{ 55 int v,next; 56 }edge[MAX*2]; 57 int head[MAX]; 58 int tot; 59 int c[MAX]; 60 int p1[MAX]; 61 int p2[MAX]; 62 int ti; 63 int dfsnum[MAX]; 64 LL sum[MAX<<2]; 65 int col[MAX<<2]; 66 void init(){ 67 mem(head,-1); 68 tot=0;ti=0; 69 } 70 71 void add_edge(int a,int b){ 72 edge[tot]=(Edge){b,head[a]}; 73 head[a]=tot++; 74 } 75 76 void dfs(int u,int fa){ 77 p1[u]=++ti; 78 dfsnum[ti]=u; 79 for(int i=head[u];i!=-1;i=edge[i].next){ 80 int v=edge[i].v; 81 if(v==fa) continue; 82 dfs(v,u); 83 } 84 p2[u]=ti; 85 } 86 87 void pushup(int rt){ 88 sum[rt]=sum[lrt]|sum[rrt]; 89 } 90 91 void pushdown(int rt){ 92 if(col[rt]){ 93 col[lrt]=col[rrt]=col[rt]; 94 sum[lrt]=sum[rrt]=(1LL<<col[rt]); 95 col[rt]=0; 96 } 97 } 98 void build(int l,int r,int rt){ 99 col[rt]=0; 100 if(l==r){ 101 sum[rt]=(1LL<<c[dfsnum[l]]); 102 return; 103 } 104 middle; 105 build(lson); 106 build(rson); 107 pushup(rt); 108 } 109 110 void update(int l,int r,int rt,int L,int R,int d){ 111 if(L<=l&&r<=R){ 112 sum[rt]=(1LL<<d); 113 col[rt]=d; 114 return; 115 } 116 middle; 117 pushdown(rt); 118 if(L<=m) update(lson,L,R,d); 119 if(R>m) update(rson,L,R,d); 120 pushup(rt); 121 } 122 123 LL query(int l,int r,int rt,int L,int R){ 124 if(L<=l&&r<=R) return sum[rt]; 125 middle; 126 LL ret=0; 127 pushdown(rt); 128 if(L<=m) ret|=query(lson,L,R); 129 if(R>m) ret|=query(rson,L,R); 130 return ret; 131 } 132 133 int main(){ 134 //freopen("in.txt","r",stdin); 135 int n,m; 136 while(cin>>n>>m){ 137 init(); 138 for(int i=1;i<=n;i++) scanf("%d",&c[i]); 139 for(int i=1;i<n;i++){ 140 int a,b; 141 scanf("%d%d",&a,&b); 142 add_edge(a,b); 143 add_edge(b,a); 144 } 145 dfs(1,-1); 146 build(1,n,1); 147 //cout<<query(1,n,1,p1[6],p2[6]); 148 while(m--){ 149 int op,a; 150 scanf("%d%d",&op,&a); 151 if(op==1){ 152 int cc; 153 scanf("%d",&cc); 154 update(1,n,1,p1[a],p2[a],cc); 155 } 156 else { 157 LL k=query(1,n,1,p1[a],p2[a]); 158 //cout<<k<<" "; 159 int num=0; 160 while(k){ 161 int tmp=k%2; 162 k/=2; 163 num+=tmp; 164 //if(tmp) cout<<tmp<<" "; 165 } 166 printf("%d ",num); 167 } 168 } 169 } 170 return 0; 171 }