[BZOJ 1086][SCOI2005]王室联邦
最近想捉一下树分块，这道题肯定是要做的啦~
这个题的方法就是蜜汁贪心，在其他树分块的题目中也有应用。
代码：
/**************************************************************
Problem: 1086
User: danihao123
Language: C++
Result: Accepted
Time:16 ms
Memory:880 kb
****************************************************************/
#include <cstdio>
#include <stack>
using std::stack;
const int maxn=1005;
const int maxm=maxn*2;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int belong[maxn],cap[maxn];
int block_cnt=0;
stack<int> S;
int B;
void DFS(int u,int fa){
int siz=S.size();
for(int i=first[u];i;i=next[i]){
int v=to[i];
if(v==fa){
continue;
}
DFS(v,u);
if((S.size()-siz)>=B){
block_cnt++;
cap[block_cnt]=u;
while(S.size()>siz){
int x=S.top();S.pop();
belong[x]=block_cnt;
}
}
}
S.push(u);
}
int main(){
register int i;
bool OK;
int n,u,v;
scanf("%d%d",&n,&B);
for(i=1;i<=(n-1);i++){
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
if(n<B){
puts("0");
return 0;
}
DFS(1,0);
while(!S.empty()){
int x=S.top();S.pop();
belong[x]=block_cnt;
}
printf("%d\n",block_cnt);
OK=false;
for(i=1;i<=n;i++){
if(OK){
putchar(' ');
}
OK=true;
printf("%d",belong[i]);
}
putchar('\n');
OK=false;
for(i=1;i<=block_cnt;i++){
if(OK){
putchar(' ');
}
OK=true;
printf("%d",cap[i]);
}
putchar('\n');
return 0;
}
[BZOJ 1009][HNOI2008]GT考试
好劲啊这题……
首先先想DP的做法，我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex]，有多少种方案使得追加上一个数后匹配[tex][1,j][/tex]，这个用KMP可以很方便的求出（事实上暴力也可以）。
然后再来看DP的做法，转移方程大致是这样的：
[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]
但是n非常大，这么做注定要TLE。
不过看这个转移方程，是不是和矩阵乘法的定义很像？是的。
我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值，我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现：
[tex]D_i\times P=D_{i+1}[/tex]
由于矩阵乘法满足结合律，所以：
[tex]D_n=D_0\times P^n[/tex]
很明显可以快速幂搞出来。
代码：
/**************************************************************
Problem: 1009
User: danihao123
Language: C++
Result: Accepted
Time:80 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
register int i,j,k;
Matrix C;
CL_ARR(C,0);
REP(i,m){
REP(j,p){
REP(k,n){
C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
}
}
}
CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
Matrix a,temp;
register int i;
CL_ARR(a,0);
memcpy(a,A,sizeof(a));
CL_ARR(temp,0);
REP(i,m){
temp[i][i]=1;
}
while(p){
if(1&p){
MatrixMul(temp,a,m,m,m,temp);
}
p>>=1;
MatrixMul(a,a,m,m,m,a);
}
CP_ARR(temp,res);
}
char buf[25];
int f[25];
int main(){
register int i,u,j;
register ull ret=0;
ull n;
int m;
Matrix ans,P;
scanf("%llu%d%llu",&n,&m,&MOD);
scanf("%s",buf+1);
CL_ARR(ans,0);
ans[0][0]=1;
CL_ARR(P,0);
P[0][0]=9;P[0][1]=1;
// f[0]=f[1]=0;
for(i=1;i<m;i++){
u=f[i];
while(u && buf[u+1]!=buf[i+1]){
u=f[u];
}
if(buf[u+1]==buf[i+1]){
f[i+1]=u+1;
}else{
f[i+1]=0;
}
for(j=0;j<10;j++){
u=i;
while(u && buf[u+1]!=j+'0'){
u=f[u];
}
if(buf[u+1]==j+'0'){
P[i][u+1]=(P[i][u+1]+1)%MOD;
}else{
P[i][0]=(P[i][0]+1)%MOD;
}
}
}
MatrixPow(P,m,n,P);
MatrixMul(ans,P,1,m,m,ans);
for(i=0;i<m;i++){
ret=(ret+ans[0][i])%MOD;
}
printf("%llu\n",ret);
return 0;
}
[BZOJ 1798]维护序列
万年不更的zzs出现了……
这个题以前竟然没做……近几天做了一下，首交竟然unAC……看样子是我真不会线段树了。
这题不难，唯一需要注意的是乘法标记对加法标记也有影响，而且下传要乘法优先。
代码（警告：此代码exciting）：
/**************************************************************
Problem: 1798
User: danihao123
Language: C++
Result: Accepted
Time:7696 ms
Memory:10980 kb
****************************************************************/
#include <cstdio>
typedef long long ll;
const int maxn=100005;
ll ha;
struct Node{
ll sumv;
int L,R;
ll addv,mulv;
Node *lc,*rc;
Node(ll v,int pos){
sumv=v%ha;
addv=0;
mulv=1;
L=R=pos;
lc=rc=NULL;
}
Node(Node *l,Node *r,int Le,int Ri){
sumv=0;
addv=0;
mulv=1;
L=Le;
R=Ri;
lc=l;
rc=r;
}
void paint_add(ll v){
v=v%ha;
addv=(addv+v)%ha;
ll add_v=(v*((R-L+1)%ha))%ha;
sumv=(sumv+add_v)%ha;
}
void paint_mul(ll v){
v=v%ha;
addv=(addv*v)%ha;
mulv=(mulv*v)%ha;
sumv=(sumv*v)%ha;
}
void maintain(){
if(lc!=NULL && rc!=NULL){
sumv=(lc->sumv+rc->sumv)%ha;
}
}
void pushdown(){
if(mulv!=1){
if(lc!=NULL){
lc->paint_mul(mulv);
}
if(rc!=NULL){
rc->paint_mul(mulv);
}
mulv=1;
}
if(addv!=0){
if(lc!=NULL){
lc->paint_add(addv);
}
if(rc!=NULL){
rc->paint_add(addv);
}
addv=0;
}
}
};
ll A[maxn];
void build_tree(Node* &o,int L,int R){
if(L==R){
o=new Node(A[L],L);
}else{
int M=L+(R-L)/2;
Node *lc,*rc;
build_tree(lc,L,M);
build_tree(rc,M+1,R);
o=new Node(lc,rc,L,R);
o->maintain();
}
}
Node *root;
int ql,qr;
ll v;
ll query_sum(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
return o->sumv;
}else{
int M=L+(R-L)/2;
ll ans=0;
if(ql<=M){
ans=(ans+query_sum(o->lc))%ha;
}
if(qr>M){
ans=(ans+query_sum(o->rc))%ha;
}
return ans;
}
}
void update_add(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
o->paint_add(v);
}else{
int M=L+(R-L)/2;
if(ql<=M){
update_add(o->lc);
}
if(qr>M){
update_add(o->rc);
}
o->maintain();
}
}
void update_mul(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
o->paint_mul(v);
}else{
int M=L+(R-L)/2;
if(ql<=M){
update_mul(o->lc);
}
if(qr>M){
update_mul(o->rc);
}
o->maintain();
}
}
int main(){
register int i;
int n,m,op;
scanf("%d%lld",&n,&ha);
// ha=0x7fffffff;
for(i=1;i<=n;i++){
scanf("%lld",&A[i]);
}
build_tree(root,1,n);
scanf("%d",&m);
while(m--){
scanf("%d%d%d",&op,&ql,&qr);
if(ha==1){
if(op==3){
puts("0");
}else{
scanf("%lld",&v);
}
continue;
}
if(op==1){
scanf("%lld",&v);
update_mul(root);
}else{
if(op==2){
scanf("%lld",&v);
update_add(root);
}else{
printf("%lld\n",query_sum(root));
}
}
}
return 0;
}
[BZOJ 2186]沙拉公主的困惑
这个题啊……亦可赛艇！
答案是[tex]\varphi(m!)*n!/m![/tex]。原因很简单，把[tex][1,n!][/tex]分成长度为[tex]m![/tex]的若干段，除去第一段外每一段中与[tex]m![/tex]互质的数[tex]k[/tex]肯定满足[tex](k\bmod m!,m!)=1[/tex]（否则，[tex]k[/tex]和[tex]m![/tex]就会有大于一的公因子了)。所以说每一段内与[tex]m![/tex]互质的数都有[tex]\varphi(m!)[/tex]个。
麻烦好像就在于求一个阶乘的欧拉函数。考虑一个新乘上的数能给答案带来的贡献——如果这个数是合数，它的所有因子在前面都有了，只能把他自己贡献出来；如果这个数是质数（假设为[tex]p[/tex]），出了贡献自己以外还会贡献一个[tex](1-1/p)[/tex]，最后乘起来就是贡献了[tex]p-1[/tex]。筛一遍素数再递推一下就好辣~
并且……[tex]n-m[/tex]可能非常大，所以说除去[tex]m![/tex]那块要用逆元做。
（顺便说下阶乘也要递推）
代码：
/**************************************************************
Problem: 2186
User: danihao123
Language: C++
Result: Accepted
Time:9408 ms
Memory:166836 kb
****************************************************************/
#include <cstdio>
#include <cmath>
typedef unsigned long long ull;
const int maxn=10000000;
ull R;
bool vis[maxn+5];
inline void sievePrime(){
register int i,j,m=sqrt(maxn+0.5);
for(i=2;i<=m;i++)
if(!vis[i])
for(j=i*i;j<=maxn;j+=i)
vis[j]=true;
}
ull fac[maxn+5];
inline void sieveFac(){
register int i;
fac[0]=1%R;
for(i=1;i<=maxn;i++)
fac[i]=(fac[i-1]*(i%R))%R;
}
ull phifac[maxn+5];
inline void sievePhiFac(){
register int i;
phifac[1]=1%R;
for(i=2;i<=maxn;i++){
if(vis[i])
phifac[i]=(phifac[i-1]*(i%R))%R;
else
phifac[i]=(phifac[i-1]*((i%R-1%R+R)%R))%R;
}
}
void exgcd(ull a,ull b,ull& d,ull& x,ull& y){
if(!b){
d=a;
x=1;
y=0;
}else{
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
ull inv(ull a){
ull d,x,y;
exgcd(a,R,d,x,y);
return (x+R)%R;
}
int main(){
int T;
int n,m;
scanf("%d%llu",&T,&R);
sievePrime();
sieveFac();
sievePhiFac();
while(T--){
scanf("%d%d",&n,&m);
printf("%llu\n",(phifac[m]*((fac[n]*inv(fac[m]))%R))%R);
}
return 0;
}
[BZOJ 1051]受欢迎的牛
Tarjan缩点第一题……
很容易想到找出度为0的点（当且仅当这样的点有一个时有解），但是在有环图上这个方法会失效。
处理方法是，用Tarjan的强联通分量算法求出所有SCC，然后把每个SCC缩成一个点，然后再在缩点之后的图上求解即可（这个图是DAG。原因很简单，要是有环还能接着缩）。
代码：
/**************************************************************
Problem: 1051
User: danihao123
Language: C++
Result: Accepted
Time:72 ms
Memory:1692 kb
****************************************************************/
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=50005;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int pre[maxn],low[maxn],sccno[maxn],sccsiz[maxn];
stack<int> S;
int dfs_clk=0,scc_cnt=0;
void dfs(int x){
dfs_clk++;
pre[x]=low[x]=dfs_clk;
S.push(x);
int i,u;
for(i=first[x];i;i=next[i]){
u=to[i];
if(!pre[u]){
dfs(u);
low[x]=min(low[x],low[u]);
}else{
if(!sccno[u])
low[x]=min(low[x],pre[u]);
}
}
if(low[x]==pre[x]){
scc_cnt++;
sccsiz[scc_cnt]=0;
while(true){
u=S.top();
S.pop();
sccno[u]=scc_cnt;
sccsiz[scc_cnt]++;
if(u==x)
break;
}
}
}
int n;
inline void Tarjan(){
register int i;
for(i=1;i<=n;i++)
if(!pre[i])
dfs(i);
}
bool Out[maxn];
int main(){
int m,u,v;
register int i,j,ans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
AddEdge(u,v);
}
Tarjan();
for(i=1;i<=n;i++){
for(j=first[i];j;j=next[j]){
u=to[j];
if(sccno[i]!=sccno[u])
Out[sccno[i]]=true;
}
}
for(i=1;i<=scc_cnt;i++){
if(!Out[i]){
if(ans){
ans=0;
break;
}
ans=sccsiz[i];
}
}
if(n==1)
ans=0;
printf("%d\n",ans);
return 0;
}
[BZOJ 3172]单词
首先……出题人语文不太好……估计和我这种语文很差的人还有差距……
这个提的意思是，给你若干个单词，输出每个单词在所有单词（而不是把所有单词连起来）中出现的次数。
然后肯定要AC自动机上失配函数搞一波辣……把BFS序倒过来搜，传递出现次数即可。还有这个题的数据范围好像也比给出的小很多……
代码：
/**************************************************************
Problem: 3172
User: danihao123
Language: C++
Result: Accepted
Time:232 ms
Memory:115080 kb
****************************************************************/
#include <cstdio>
#include <cstring>
const int maxn=205;
const int maxnode=1*1e6+5;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int cnt[maxnode];
namespace ACAutomate{
// Trie
const int sigma_size=26;
int Tree[maxnode][sigma_size];
int siz;
inline int idx(char c){
return c-'a';
}
void InitAC(){
siz=0;
CL_ARR(Tree[0],0);
}
int Insert(char *s){
register int i,n=strlen(s);
register int u=0,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
cnt[u]++;
}
return u;
}
// AC Automate
int f[maxnode];
int Q[maxnode];
void InitFail(){
register int i,u,x,v,head=0,tail=0;
f[0]=0;
REP(i,sigma_size){
u=Tree[0][i];
if(u){
f[u]=0;
Q[tail++]=u;
}
}
while(head<tail){
u=Q[head];
head++;
REP(i,sigma_size){
x=Tree[u][i];
if(!x){
continue;
}
Q[tail++]=x;
v=f[u];
while(v && !Tree[v][i])
v=f[v];
f[x]=Tree[v][i];
}
}
for(i=tail-1;i>=0;i--)
cnt[f[Q[i]]]+=cnt[Q[i]];
}
};
char buf[maxnode];
int pos[maxn];
int main(){
int n;
register int i;
scanf("%d",&n);
ACAutomate::InitAC();
REP_B(i,n){
scanf("%s",buf);
pos[i]=ACAutomate::Insert(buf);
}
ACAutomate::InitFail();
REP_B(i,n){
printf("%d\n",cnt[pos[i]]);
}
return 0;
}
[BZOJ 1212]L语言
这个感觉本质上和那个Remember a Word很像吧……
不过这个只是求最长可行前缀，递推即可。
代码：
/**************************************************************
Problem: 1212
User: danihao123
Language: C++
Result: Accepted
Time:660 ms
Memory:45072 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1048581;
const int maxW=4005,maxL=105;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
vector<int> AnsList;
namespace Trie{
const int maxnode=400005;
const int sigma_siz=26;
int Tree[maxnode][sigma_siz];
int val[maxnode];
int siz;
inline int idx(char c){
return c-'a';
}
inline void InitTrie(){
siz=0;
val[0]=0;
CL_ARR(Tree[0],0);
}
void Insert(char *s,int v){
register int u=0,n=strlen(s);
register int i,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
val[siz]=0;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
}
val[u]=v;
}
void Query(char *s,int len){
register int i,c,u=0;
AnsList.clear();
REP(i,len){
if(!s[i])
break;
c=idx(s[i]);
if(!Tree[u][c])
break;
u=Tree[u][c];
if(val[u])
AnsList.push_back(val[u]);
}
}
};
char Text[maxn];
int len[maxW];
char buf[maxL];
bool d[maxn];
int main(){
int n,m;
int length;
register int i,j,k;
bool flag;
Trie::InitTrie();
scanf("%d%d",&n,&m);
REP_B(i,n){
scanf("%s",buf);
len[i]=strlen(buf);
Trie::Insert(buf,i);
}
REP_B(i,m){
scanf("%s",Text);
length=strlen(Text);
CL_ARR(d,0);
d[0]=true;
for(j=0;j<=length;j++){
if(d[j]){
Trie::Query(Text+j,length-j);
REP(k,AnsList.size()){
d[j+len[AnsList[k]]]=true;
}
}
}
flag=false;
for(j=length;j>=0;j--){
if(d[j]){
flag=true;
printf("%d\n",j);
break;
}
}
if(!flag)
puts("0");
}
return 0;
}
[BZOJ 2190]仪仗队
这个题啊……有规律可循。
我们可以发现，关于答案[tex]a[/tex]有如下规律：
[tex]a+1=2\mul (\Sigma_{i=2}^{n-1}\varphi(i)+2)[/tex]
然后筛法求欧拉函数即可（我听说神犇们都用了杜教筛哎）
代码：
/**************************************************************
Problem: 2190
User: danihao123
Language: C++
Result: Accepted
Time:28 ms
Memory:976 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40005;
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
int phi[maxn];
int n;
void sieve(){
register int i,j;
phi[1]=1;
CUS_REP(i,2,n)
if(!phi[i])
for(j=i;j<=n;j+=i){
if(!phi[j])
phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
int main(){
register int i,ans=2;
scanf("%d",&n);
sieve();
/*
#ifdef DEBUG
CUS_REP(i,1,n)
printf("%d\n",phi[i]);
#endif
*/
CUS_REP(i,2,n-1)
ans+=phi[i];
printf("%d\n",ans*2-1);
return 0;
}
[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查
这个是一道题啊……不过都是挺经典的问题……
建图是这样的：支持0的从[tex]S[/tex]向此点连一条容量为1的边，支持1的就向[tex]T[/tex]连一条长度为1的边，朋友之间连一条长度为1的边。跑一遍最小割即可。
这个的解释？最优情况下任何人违背自己的意见都是因为怕和朋友冲突，和朋友冲突则是因为没有违背自己的意见（废话）。所以拆了最小割就解决掉了所有冲突问题。
代码：
/**************************************************************
Problem: 2768
User: danihao123
Language: C++
Result: Accepted
Time:60 ms
Memory:7668 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=305;
namespace Dinic{
struct Edge{
int u,v,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int s,t;
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int cur[maxn],d[maxn];
bool bfs(){
register int i,u;
queue<int> Q;
memset(vis,0,sizeof(vis));
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
d[e.v]=d[u]+1;
Q.push(e.v);
vis[e.v]=true;
}
}
}
return vis[t];
}
int dfs(int x,int a){
if(x==t || a==0)
return a;
int f,flow=0;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if((d[x]+1==d[e.v]) && ((f=dfs(e.v,min(a,e.cap-e.flow)))>0)){
flow+=f;
e.flow+=f;
edges[G[x][i]^1].flow-=f;
a-=f;
if(a==0)
break;
}
}
return flow;
}
int MinCut(int S,int T){
register int ans=0;
s=S;
t=T;
while(bfs()){
memset(cur,0,sizeof(cur));
ans+=dfs(s,0x7fffffff);
}
return ans;
}
};
int main(){
int n,m;
int u,v;
register int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&u);
if(!u){
Dinic::AddEdge(0,i,1);
}else{
Dinic::AddEdge(i,n+1,1);
}
}
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
Dinic::AddEdge(u,v,1);
Dinic::AddEdge(v,u,1);
}
printf("%d\n",Dinic::MinCut(0,n+1));
return 0;
}
[BZOJ 3531]旅行
发现自己好久没写树链剖分了……唉……
言归正传，这道题很容易想到的做法就是每种宗教开一个线段树，到各个宗教的线段树里面操作即可。
很可惜，直接开线段树的话肯定会MLE。我们可以考虑动态开点，对于不需要的点一律不开。这样内存消耗量就大减了。
注意一些细节：
- 查询时判断当前结点是不是NULL。
- 删除前最好判断一下这个结点是不是NULL吧，以防万一。
- 删除操作时，如果结点没有用了，就删。但是注意，记得delete前要把原指针设为NULL，直接delete会引起悬垂指针问题导致爆炸！
代码：
/**************************************************************
Problem: 3531
User: danihao123
Language: C++
Result: Accepted
Time:10404 ms
Memory:34872 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n;
namespace SegmentTree{
struct Node{
int sumv,maxv;
Node *lc,*rc;
Node(){
sumv=maxv=0;
lc=rc=NULL;
}
void maintain(){
if(lc!=NULL){
if(rc!=NULL){
sumv=lc->sumv+rc->sumv;
maxv=max(lc->maxv,rc->maxv);
}else{
sumv=lc->sumv;
maxv=lc->maxv;
}
}else{
if(rc!=NULL){
sumv=rc->sumv;
maxv=rc->maxv;
}
}
}
};
Node* T[maxn];
int p,v;
void _Delete(Node* &o,int L,int R){
if(o==NULL)
return;
if(L==R){
Node *temp=o;
o=NULL;
delete temp;
}else{
int M=L+(R-L)/2;
if(p<=M)
_Delete(o->lc,L,M);
else
_Delete(o->rc,M+1,R);
if(o->lc==NULL && o->rc==NULL){
Node *temp=o;
o=NULL;
delete temp;
}else{
o->maintain();
}
}
}
inline void Delete(int c,int pos){
p=pos;
_Delete(T[c],1,n);
}
void _Insert(Node* &o,int L,int R){
if(o==NULL)
o=new Node();
if(L==R){
o->sumv=o->maxv=v;
}else{
int M=L+(R-L)/2;
if(p<=M)
_Insert(o->lc,L,M);
else
_Insert(o->rc,M+1,R);
}
o->maintain();
}
inline void Insert(int c,int pos,int value){
p=pos;
v=value;
_Insert(T[c],1,n);
}
int ql,qr;
int _query_max(Node *o,int L,int R){
if(o==NULL)
return 0;
if(ql<=L && R<=qr)
return o->maxv;
int M=L+(R-L)/2,ans=0;
if(ql<=M)
ans=max(ans,_query_max(o->lc,L,M));
if(qr>M)
ans=max(ans,_query_max(o->rc,M+1,R));
return ans;
}
inline int query_max(int c,int l,int r){
ql=l;
qr=r;
return _query_max(T[c],1,n);
}
int _query_sum(Node *o,int L,int R){
if(o==NULL)
return 0;
if(ql<=L && R<=qr)
return o->sumv;
int M=L+(R-L)/2,ans=0;
if(ql<=M)
ans+=_query_sum(o->lc,L,M);
if(qr>M)
ans+=_query_sum(o->rc,M+1,R);
return ans;
}
inline int query_sum(int c,int l,int r){
ql=l;
qr=r;
return _query_sum(T[c],1,n);
}
};
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_tot=0;
inline void AddEdge(int u,int v){
graph_tot++;
next[graph_tot]=first[u];
first[u]=graph_tot;
to[graph_tot]=v;
}
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
bool vis[maxn];
void dfs_1(int x,int father,int depth){
vis[x]=true;
fa[x]=father;
dep[x]=depth;
siz[x]=1;
int i,temp,max_siz=0;
GRAPH_REP(i,x){
temp=to[i];
if(!vis[temp]){
dfs_1(temp,x,depth+1);
siz[x]+=siz[temp];
if(siz[temp]>max_siz){
son[x]=temp;
max_siz=siz[temp];
}
}
}
}
int hld_cnt=0;
int rlg[maxn];
int d[maxn];
int tid[maxn],top[maxn];
void dfs_2(int x,int a){
vis[x]=true;
top[x]=a;
tid[x]=++hld_cnt;
SegmentTree::Insert(rlg[x],hld_cnt,d[x]);
if(son[x])
dfs_2(son[x],a);
else
return;
int i,temp;
GRAPH_REP(i,x){
temp=to[i];
if(!vis[temp]){
dfs_2(temp,temp);
}
}
}
int query_max(int c,int x,int y){
if(top[x]==top[y]){
if(tid[x]>tid[y])
swap(x,y);
return SegmentTree::query_max(c,tid[x],tid[y]);
}
if(dep[top[x]]<dep[top[y]])
swap(x,y);
return max(SegmentTree::query_max(c,tid[top[x]],tid[x]),query_max(c,fa[top[x]],y));
}
int query_sum(int c,int x,int y){
if(top[x]==top[y]){
if(tid[x]>tid[y])
swap(x,y);
return SegmentTree::query_sum(c,tid[x],tid[y]);
}
if(dep[top[x]]<dep[top[y]])
swap(x,y);
return SegmentTree::query_sum(c,tid[top[x]],tid[x])+query_sum(c,fa[top[x]],y);
}
inline void Replace(int pos,int direction){
int c=rlg[pos];
SegmentTree::Delete(c,tid[pos]);
SegmentTree::Insert(direction,tid[pos],d[pos]);
rlg[pos]=direction;
}
inline void Update(int pos,int v){
d[pos]=v;
SegmentTree::Insert(rlg[pos],tid[pos],v);
}
int main(){
register int i;
int q,u,v;
char buf[5];
scanf("%d%d",&n,&q);
REP_B(i,n){
scanf("%d%d",&d[i],&rlg[i]);
}
REP_B(i,n-1){
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
dfs_1(1,0,1);
memset(vis,0,sizeof(vis));
dfs_2(1,1);
while(q--){
memset(buf,0,sizeof(buf));
scanf("%s%d%d",buf,&u,&v);
if(buf[0]=='C'){
if(buf[1]=='W'){
Update(u,v);
}else{
Replace(u,v);
}
}else{
if(buf[1]=='M'){
printf("%d\n",query_max(rlg[u],u,v));
}else{
printf("%d\n",query_sum(rlg[u],u,v));
}
}
}
return 0;
}
