You are given a tree with N nodes. The tree nodes are numbered from 1 to N and have colors C1, C2,
. . . , CN initially. You have to handle M instructions on the tree of the following forms:
• 0 u c: Change the color of node u to c.
• 1 u v: Output the maximum number of times a color appeared on the unique path from node u
to node v.
Input
The first line of input contains T (1 ≤ T ≤ 10) which is the number of test cases. The first line of each
test case contains two integers N and M (1 ≤ N, M ≤ 105
). Next line contains N space separated
integers C1, C2, . . . , CN (1 ≤ Ci ≤ 10) denoting the initial colors of the nodes. Each of the next N − 1
lines contain two integers a and b (1 ≤ a, b ≤ N and a ̸= b) meaning that there is an edge between
node a and node b. Each of the next M lines contains an instruction of one of the two forms described
above. For all the instructions: 1 ≤ u, v ≤ N and 1 ≤ c ≤ 10.
Output
For each of the second type instruction output the answer in one line.
Sample Input
2
5 6
3 2 1 2 3
1 2
2 3
2 4
1 5
1 3 5
0 1 1
0 2 1
1 3 5
0 2 4
1 2 4
2 1
5 6
1 2
1 2 2
Sample Output
2
3
1
1
题意：给你一颗树，树上的每个节点都有颜色，颜色编号在1-10之间，给出两种操作
操作一：将树上x点的颜色搞成val
操作二：求点u到点v路径上最多的颜色有几个
题解：颜色很少，所以不用树上莫队，可以建10棵线段树，如果一个点的颜色为ai，则在ai编号的线段树上该点为1，其他编号的树上该点为0
然后每次跑路径的时候跑十遍，记下路径和最大的一种颜色输出，就是答案了,emmm,真暴力啊QAQ
因为涉及到树上路径，所以树链剖分即可了
代码如下：
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson root<<1
#define rson root<<1|1
using namespace std; struct seg_tree
{
struct node
{
int l,r,sum;
} tr[]; void push_up(int root)
{
tr[root].sum=tr[lson].sum+tr[rson].sum;
} void build(int root,int l,int r)
{
if(l==r)
{
tr[root].l=l;
tr[root].r=r;
return ;
}
tr[root].l=l;
tr[root].r=r;
int mid=(l+r)>>;
build(lson,l,mid);
build(rson,mid+,r);
} void update(int root,int pos,int val)
{
if(tr[root].l==pos&&tr[root].r==pos)
{
tr[root].sum=val;
return ;
}
int mid=(tr[root].l+tr[root].r)>>;
if(pos<=mid)
{
update(lson,pos,val);
}
else
{
update(rson,pos,val);
}
push_up(root);
} int query(int root,int l,int r)
{
if(tr[root].l==l&&tr[root].r==r)
{
return tr[root].sum;
}
int mid=(tr[root].l+tr[root].r)>>;
if(mid<l)
{
return query(rson,l,r);
}
else
{
if(mid>=r)
{
return query(lson,l,r);
}
else
{
return query(lson,l,mid)+query(rson,mid+,r);
}
}
} void dfs(int root,int l,int r)
{
if(l==r)
{
return ;
} int mid=(l+r)>>;
dfs(lson,l,mid);
dfs(rson,mid+,r);
}
} tree[]; vector<int> g[];
int fa[],deep[],size[],son[],id[],c[],w[],top[],cnt; void dfs1(int now,int f,int dep)
{
fa[now]=f;
deep[now]=dep;
size[now]=;
int maxson=-;
for(int i=; i<g[now].size(); i++)
{
if(g[now][i]==f)
{
continue;
}
dfs1(g[now][i],now,dep+);
size[now]+=size[g[now][i]];
if(size[g[now][i]]>maxson)
{
maxson=size[g[now][i]];
son[now]=g[now][i];
}
}
} void dfs2(int now,int topf)
{
id[now]=++cnt;
w[cnt]=c[now];
top[now]=topf;
if(!son[now])
{
return ;
}
dfs2(son[now],topf);
for(int i=; i<g[now].size(); i++)
{
if(fa[now]==g[now][i]||g[now][i]==son[now])
{
continue;
}
dfs2(g[now][i],g[now][i]);
}
} void point_update(int u,int val)
{
for(int i=; i<=; i++)
{
if(val==i)
{
tree[i].update(,id[u],);
}
else
{
tree[i].update(,id[u],);
}
}
} int path_query(int u,int v,int val)
{
int ans=;
while(top[u]!=top[v])
{
if(deep[top[u]]<deep[top[v]])
{
swap(u,v);
}
ans+=tree[val].query(,id[top[u]],id[u]);
u=fa[top[u]];
}
if(deep[u]>deep[v])
{
swap(u,v);
}
ans+=tree[val].query(,id[u],id[v]);
return ans;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
memset(tree,,sizeof(tree));
memset(fa,,sizeof(fa));
memset(son,,sizeof(son));
memset(deep,,sizeof(deep));
memset(size,,sizeof(size));
memset(id,,sizeof(id));
memset(c,,sizeof(c));
memset(w,,sizeof(w));
memset(top,,sizeof(top));
cnt=;
for(int i=;i<=;i++)
{
g[i].clear();
}
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++)
{
scanf("%d",&c[i]);
}
for(int i=; i<n; i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs1(,,);
dfs2(,);
for(int i=; i<=; i++)
{
tree[i].build(,,n);
}
for(int i=; i<=n; i++)
{
tree[w[i]].update(,i,);
}
for(int i=; i<=m; i++)
{
int kd,l,r;
scanf("%d%d%d",&kd,&l,&r);
if(kd==)
{
int ans=;
for(int j=; j<=; j++)
{
ans=max(ans,path_query(l,r,j));
}
printf("%d\n",ans);
}
else
{
if(kd==)
{
point_update(l,r);
} }
}
} }