[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; }