题意：给一棵树，每个节点都有颜色，最多有10种颜色
定义：两种操作
0 u c 把编号为u的节点颜色改为c
1 u v 求树上u~v的路径中，颜色出现的次数的最大值
思路：用color[i][j]记录根节点到节点i，j颜色的出现次数。 c[i]记录i的颜色
先用ST求LCA 对于每个询问 ans=max(color[u][i]+color[v][i]-2*color[LCA(u,v)][i]+c[LCA(u,v)]==i)
然后dfs，记录开始时间low[i]和结束时间high[i]，更改操作相当于，更改一个区间[low[i],high[i]] 线段树求解
1 #include<iostream>
2 #include<ctime>
3 #include<cstdio>
4 #include<cstring>
5 #include<cmath>
6 using namespace std;
7 #define MAXN 100001
8 struct node
9 {
10 int num;
11 node *next;
12 };
13 struct number
14 {
15 int left,right;
16 bool mark;
17 int sum[11];
18 };
19 int ans[11];
20 int father[MAXN];
21 int Log[2*MAXN];
22 int n,m,T;
23 int d[MAXN];
24 int euler[2*MAXN];
25 int low[MAXN],high[MAXN];
26 int color[MAXN][11];
27 int c[MAXN];
28 number tree[4*MAXN];
29 node *graph[MAXN];
30 node memo[2*MAXN];
31 int home[MAXN];
32 int sparse_table[2*MAXN][20];
33 int sparse_table_num[2*MAXN][20];
34 int top,label;
35 void LOG()
36 {
37 Log[1]=0;
38 for(int i=2;i<2*MAXN;i++) Log[i]=Log[i/2]+1;
39 }
40 void add(int x,int y)
41 {
42 node *p=&memo[top++];
43 p->num=y; p->next=graph[x]; graph[x]=p;
44 p=&memo[top++];
45 p->num=x; p->next=graph[y]; graph[y]=p;
46 }
47 void dfs(int i)
48 {
49 low[i]=++label;
50 for(int j=1;j<=10;j++)
51 color[low[i]][j]+=color[low[father[i]]][j];
52 color[low[i]][c[i]]++;
53 euler[++top]=i;
54 home[i]=top;
55 for(node *p=graph[i];p;p=p->next)
56 {
57 if(!low[p->num])
58 {
59 father[p->num]=i;
60 d[p->num]=d[i]+1;
61 dfs(p->num);
62 euler[++top]=i;
63 }
64 }
65 high[i]=label;
66 }
67 void segment(int i)
68 {
69 if(tree[i].left==tree[i].right)
70 {
71 for(int j=1;j<=10;j++)
72 tree[i].sum[j]=color[tree[i].left][j];
73 return ;
74 }
75 int mid=(tree[i].left+tree[i].right)/2;
76 tree[2*i].left=tree[i].left; tree[2*i].right=mid;
77 tree[2*i+1].left=mid+1; tree[2*i+1].right=tree[i].right;
78 segment(2*i); segment(2*i+1);
79 }
80 void push_down(int i)
81 {
82 for(int j=1;j<=10;j++)
83 {
84 if(tree[i].sum[j]!=0&&tree[i].left!=tree[i].right)
85 {
86 tree[2*i].mark=tree[2*i+1].mark=1;
87 tree[2*i].sum[j]+=tree[i].sum[j];
88 tree[2*i+1].sum[j]+=tree[i].sum[j];
89 }
90 tree[i].sum[j]=0;
91 }
92 tree[i].mark=0;
93 }
94 void change(int i,int x,int y,int k_add,int k_minus)
95 {
96 if(tree[i].left==x&&tree[i].right==y)
97 {
98 tree[i].mark=1;
99 tree[i].sum[k_add]++;
100 tree[i].sum[k_minus]--;
101 return ;
102 }
103 if(tree[i].mark)
104 push_down(i);
105 int mid=(tree[i].left+tree[i].right)/2;
106 if(y<=mid) change(2*i,x,y,k_add,k_minus);
107 else if(x>mid) change(2*i+1,x,y,k_add,k_minus);
108 else
109 {
110 change(2*i,x,mid,k_add,k_minus);
111 change(2*i+1,mid+1,y,k_add,k_minus);
112 }
113 }
114 void search(int i,int x,int multi)
115 {
116 if(tree[i].left==tree[i].right)
117 {
118 for(int j=1;j<=10;j++)
119 ans[j]+=multi*tree[i].sum[j];
120 return ;
121 }
122 if(tree[i].mark)
123 push_down(i);
124 int mid=(tree[i].left+tree[i].right)/2;
125 if(x<=mid) search(2*i,x,multi);
126 else search(2*i+1,x,multi);
127 }
128 void build_sparse_table()
129 {
130 int i,j;
131 for(i=1;i<=top;i++)
132 {
133 sparse_table[i][0]=d[euler[i]];
134 sparse_table_num[i][0]=euler[i];
135 }
136 for(j=1;(1<<j)<=top;j++)
137 {
138 for(i=1;i<=top-(1<<j)+1;i++)
139 {
140 if(sparse_table[i][j-1]<sparse_table[i+(1<<(j-1))][j-1])
141 {
142 sparse_table[i][j]=sparse_table[i][j-1];
143 sparse_table_num[i][j]=sparse_table_num[i][j-1];
144 }
145 else
146 {
147 sparse_table[i][j]=sparse_table[i+(1<<(j-1))][j-1];
148 sparse_table_num[i][j]=sparse_table_num[i+(1<<(j-1))][j-1];
149 }
150 }
151 }
152 }
153 int LCA(int x,int y)
154 {
155 if(x>y)
156 {
157 int t;
158 t=x; x=y; y=t;
159 }
160 int z=Log[y-x+1];
161 if(sparse_table[x][z]<sparse_table[y-(1<<z)+1][z])
162 return sparse_table_num[x][z];
163 else return sparse_table_num[y-(1<<z)+1][z];
164 }
165 int main()
166 {
167 scanf("%d",&T);
168 int i,j,k;
169 int x,y,z;
170 LOG();
171 for(k=1;k<=T;k++)
172 {
173 top=label=0;
174 memset(low,0,sizeof(low));
175 memset(graph,0,sizeof(graph));
176 memset(tree,0,sizeof(tree));
177 memset(color,0,sizeof(color));
178 scanf("%d%d",&n,&m);
179 for(i=1;i<=n;i++)
180 {
181 scanf("%d",&x);
182 c[i]=x;
183 }
184 for(i=1;i<n;i++)
185 {
186 scanf("%d%d",&x,&y);
187 add(x,y);
188 }
189 father[1]=0;
190 d[1]=0;
191 top=0;
192 dfs(1);
193 tree[1].left=1; tree[1].right=n;
194 segment(1);
195 build_sparse_table();
196 for(i=1;i<=m;i++)
197 {
198 scanf("%d%d%d",&z,&x,&y);
199 if(z==0)
200 {
201 change(1,low[x],high[x],y,c[x]);
202 c[x]=y;
203 }
204 else
205 {
206 int fa=LCA(home[x],home[y]);
207 int MAX=0;
208 memset(ans,0,sizeof(ans));
209 search(1,low[x],1); search(1,low[y],1); search(1,low[fa],-2);
210 for(j=1;j<=10;j++)
211 {
212 if(c[fa]==j) ans[j]++;
213 if(ans[j]>MAX) MAX=ans[j];
214 }
215 printf("%d\n",MAX);
216 }
217 }
218 }
219 return 0;
220 }