Description
Solution
- 切了一道维护子树size的LCT的模板题，庆祝一下（手动滑稽）
- 首先把颜色挂在到父亲的边上（套路），那么除了每一个联通块的最顶端的点，其他点的颜色都是一样的。
- 改点的时候就修改到它的父亲的边的连通性。
- 仔细思考之后得出需要维护轻边到它的，以及当前点轻边连向它的，还有整棵Splay子树的前者的和（即子树大小和）。
- 操作的时候始终让最浅的点成为根，即操作完要makert它。
- 连边删边的时候就是把两个联通块的答案减去，修改修改，再加上整个联通块的答案。
- 还是蛮裸的。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 200005
#define ll long long
#define mo 1000000007
using namespace std;
int n,q,K,i,j,k,fa[maxn],a[maxn];
int em,e[maxn*2],nx[maxn*2],ls[maxn];
ll mul[maxn],ans[maxn];
struct opr{int x,t;opr(int _x=0,int _t=0){x=_x,t=_t;}};
vector<opr> op[maxn];
void read(int &x){
x=0; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}
ll ksm(ll x,ll y){
ll s=1;
for(;y;y/=2,x=x*x%mo) if (y&1)
s=s*x%mo;
return s;
}
void insert(int x,int y){
em++; e[em]=y; nx[em]=ls[x]; ls[x]=em;
em++; e[em]=x; nx[em]=ls[y]; ls[y]=em;
}
int D[maxn];
void BFS(){
int t=0,w=1; D[1]=1,fa[1]=n+1;
while (t<w){
int x=D[++t];
for(int i=ls[x];i;i=nx[i]) if (e[i]!=fa[x])
fa[e[i]]=x,D[++w]=e[i];
}
}
struct node{int f,tag,s[2],sz,ssz;ll q;} t[maxn];
int nroot(int x){return t[t[x].f].s[0]==x||t[t[x].f].s[1]==x;}
int get(int x){return t[t[x].f].s[1]==x;}
void downtag(int x){
if (t[x].tag){
swap(t[x].s[0],t[x].s[1]);
if (t[x].s[0]) t[t[x].s[0]].tag^=1;
if (t[x].s[1]) t[t[x].s[1]].tag^=1;
t[x].tag=0;
}
}
void upd(int x){t[x].ssz=t[x].sz+t[t[x].s[0]].ssz+t[t[x].s[1]].ssz;}
void rotate(int x){
int y=t[x].f,c=get(x);
t[y].s[c]=t[x].s[c^1],t[x].s[c^1]=y;
if (t[y].s[c]) t[t[y].s[c]].f=y;
if (nroot(y)) t[t[y].f].s[get(y)]=x;
t[x].f=t[y].f,t[y].f=x;
upd(y),upd(x);
}
int d[maxn];
void remove(int x){
while (x) {d[++d[0]]=x;if (!nroot(x)) break;x=t[x].f;}
while (d[0]) downtag(d[d[0]]),d[0]--;
}
void splay(int x){
remove(x);
int y;
while (nroot(x)){
y=t[x].f;
if (nroot(y)) {
if (get(x)==get(y)) rotate(y);
else rotate(x);
}
rotate(x);
} upd(x);
}
void access(int x){
int y=0,z;
for(;x;x=t[x].f){
splay(x);
z=t[x].s[1];
if (z){
t[x].q+=mul[t[z].ssz];
t[x].sz+=t[z].ssz;
} t[x].s[1]=y;
if (y){
t[x].q-=mul[t[y].ssz];
t[x].sz-=t[y].ssz;
}
upd(x),y=x;
}
}
void makert(int x){access(x);splay(x);t[x].tag=1;}
int findrt(int x){
access(x);
while (t[x].f) x=t[x].f;
downtag(x);
while (t[x].s[0]) x=t[x].s[0],downtag(x);
return x;
}
int main(){
freopen("ceshi.in","r",stdin);
freopen("ceshi.out","w",stdout);
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
read(n),read(q),read(K);
for(i=1;i<=n;i++) read(a[i]),op[a[i]].push_back(opr(i,0));
for(i=1;i<=n;i++)
mul[i]=ksm(i,K);
for(i=1;i<n;i++) read(j),read(k),insert(j,k);
BFS();
for(i=1;i<=q;i++){
ans[i]=-1;
char ch=getchar(); while(ch!='M'&&ch!='Q') ch=getchar();
if (ch=='M'){
read(j),read(k);
if (k!=a[j]){
op[a[j]].push_back(opr(j,0));
op[a[j]=k].push_back(opr(j,0));
}
} else read(k),op[k].push_back(opr(0,i));
}
for(i=1;i<=n;i++) op[a[i]].push_back(opr(i,0));
memset(a,0,sizeof(a));
for(i=1;i<=n+1;i++) t[i].sz=t[i].ssz=1;
for(int col=1;col<=n;col++) {
ll sum=0;
for(i=0;i<op[col].size();i++){
if (!op[col][i].t){
int x=op[col][i].x,y=fa[x],z;
if (!a[x]){
access(x),sum-=t[x].q;
z=findrt(y),access(z),sum-=t[z].q;
makert(y),splay(y);
t[x].f=y;
t[y].q+=mul[t[x].ssz];
t[y].sz+=t[x].ssz;
t[y].ssz+=t[x].ssz;
makert(z),access(z),sum+=t[z].q;
} else{
z=findrt(x),access(z),sum-=t[z].q;
makert(y),access(x),splay(x);
t[t[x].s[0]].f=0,t[x].s[0]=0;
t[x].ssz-=t[y].ssz;
access(x),sum+=t[x].q;
makert(z),access(z),sum+=t[z].q;
}
a[x]^=1;
} else ans[op[col][i].t]=sum;
}
}
for(i=1;i<=q;i++) if (ans[i]>=0)
printf("%lld
",ans[i]%mo);
}