\u867d\u7136\u8fd9\u4e00\u9898\u88ab\u5212\u5728\u4e3b\u5e2d\u6811\u4e0b\u9762\uff0c\u4f46\u662f\u4e00\u773c\u770b\u8fc7\u53bb\u8fd9\u4e0d\u5c31\u662f\u6811\u94fe\u5256\u5206\u52a8\u6001\u5f00\u70b9\u7ebf\u6bb5\u6811\u7684\u6a21\u677f\u9898\u4e48\u3002
\n\u6811\u94fe\u5256\u5206\u540e\u6211\u4eec\u8003\u8651\u5bf9\u6bcf\u4e00\u6761\u94fe\uff0c\u5efa\u5f88\u591a\u68f5\u7ebf\u6bb5\u6811\uff0c\u6bcf\u68f5\u7ebf\u6bb5\u6811\u8868\u793a\u8fd9\u6761\u94fe\u4e0a\u67d0\u79cd\u989c\u8272\u7684\u60c5\u51b5\uff0c\u7136\u540e\u5927\u529b\u5408\u5e76\u3002\u590d\u6742\u5ea6\u663e\u7136\u662f\u5bf9\u7684\u3002
\n\u5173\u952e\u662f\u5982\u4f55\u52a8\u6001\u5f00\u70b9\u3002\u672c\u8d28\u4e0a\u52a8\u6001\u5f00\u70b9\u957f\u5f97\u5c31\u548c\u4e3b\u5e2d\u6811\u5dee\u4e0d\u591a\uff08\u8fd9\u53ef\u80fd\u662f\u4e3a\u4ec0\u4e48\u8fd9\u9898\u4f1a\u88ab\u653e\u5728\u4e3b\u5e2d\u6811\u4e0b\u9762\uff09\uff0c\u4f46\u662f\u53ef\u80fd\u5b58\u5728\u5f88\u591a\u7ec6\u8282\u3002
\n\u53e6\uff1a\u6211\u7684\u7ebf\u6bb5\u6811\u533a\u95f4\u67e5\u8be2\u5199\u6210\u4f9d\u6b21\u5355\u70b9\u67e5\u8be2\uff0c\u5c45\u7136\u8dd1\u5230\u4e861.2s\uff0c\u8ba9\u6211\u4e00\u5ea6\u4ee5\u4e3a\u662f\u6211\u5e38\u6570\u95ee\u9898\u2026\u751a\u81f3\u5dee\u70b9\u5361\u8fdb\u53bb\u4e86\u3002\u7cbe\u5f69\u3002 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n\ninline int rd(){\n\tchar ch=getchar();int r=0;\n\twhile(!isdigit(ch)){ch=getchar();}\n\twhile(isdigit(ch)){r=r*10+ch-'0';ch=getchar();}\n\treturn r;\n}\nconst int N=100005;\ninline int Max(int A,int B){\n\treturn A>B?A:B;\n}\ninline void Swap(int &A,int &B){\n\tA^=B^=A^=B;\n}\nstruct ee{\n\tint v;\n\tint nxt;\n}e[N<<1];\nint h[N],et=0;\ninline void Eadd(int U,int V){\n\te[++et]=(ee){V,h[U]};\n\th[U]=et;\n}\ninline void add(int U,int V){\n\tEadd(U,V);Eadd(V,U);\n}\nint n,m;\nint val[N],clr[N],dep[N],sz[N],sn[N],fa[N],dfn[N],cnt=0,tp[N];\ninline void dfs0(int X){\n\tdep[X]=dep[fa[X]]+1;sz[X]=1;sn[X]=0;\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tif(e[i].v==fa[X]){continue;}\n\t\tfa[e[i].v]=X;\n\t\tdfs0(e[i].v);\n\t\tif(sz[e[i].v]>sz[sn[X]]){\n\t\t\tsn[X]=e[i].v;\n\t\t}\n\t\tsz[X]+=sz[e[i].v];\n\t}\n}\ninline void dfs1(int X){\n\tdfn[X]=++cnt;\n\tif(sn[X]){tp[sn[X]]=tp[X];dfs1(sn[X]);}\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tif(e[i].v==sn[X]||e[i].v==fa[X]){continue;}\n\t\ttp[e[i].v]=e[i].v;dfs1(e[i].v);\n\t}\n}\n#define MID ((L+R)>>1)\nstruct Node{\n\tint l;int r;int sm;int mx;\n}tr[4000005];\nint rt[N];\nint tcnt=0;\ninline void chg(int &NW,int L,int R,int P,int V){\n\tif(!NW){NW=++tcnt;}\n\tif(L==R){tr[NW].sm=V,tr[NW].mx=V;return;}\n\tP<=MID?(chg(tr[NW].l,L,MID,P,V)):(chg(tr[NW].r,MID+1,R,P,V));\n\ttr[NW].sm=tr[tr[NW].l].sm+tr[tr[NW].r].sm;tr[NW].mx=Max(tr[tr[NW].l].mx,tr[tr[NW].r].mx);\n}\ninline int qryMx(int X,int A,int B,int L,int R){\n\tif(A>R||B<L||!X){return 0;}\n\tif(A<=L&&B>=R){return tr[X].mx;}\/\/\u6b64\u5904\u4e0d\u5e94\u5199\u6210L==R \n\treturn Max((A<=MID?qryMx(tr[X].l,A,B,L,MID):0),(B>MID?qryMx(tr[X].r,A,B,MID+1,R):0));\n}\ninline int qrySm(int X,int A,int B,int L,int R){\n\tif(A>R||B<L||!X){return 0;}\n\tif(A<=L&&B>=R){return tr[X].sm;}\n\treturn (A<=MID?qrySm(tr[X].l,A,B,L,MID):0)+(B>MID?qrySm(tr[X].r,A,B,MID+1,R):0);\n}\ninline void ADD(int X,int P,int V){\n\tchg(rt[X],1,n,P,V);\n}\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\tfor(int i=1;i<=n;++i){\n\t\tval[i]=rd(),clr[i]=rd();\n\t}\n\tint u,v;\n\tfor(int i=1;i<n;++i){\n\t\tu=rd(),v=rd();\n\t\tadd(u,v);\n\t}\n\tsz[0]=0;fa[1]=0;\n\tdfs0(1);\n\ttp[1]=1;\n\tdfs1(1);\n\tfor(int i=1;i<=n;++i){\n\t\tADD(clr[i],dfn[i],val[i]);\n\t}\n\tchar ch[10];\n\tint x,y,c;\n\tfor(int i=1;i<=m;++i){\n\t\tstd::cin>>ch+1;\n\t\tswitch(ch[2]){\n\t\t\tcase 'C':{\n\t\t\t\tx=rd(),y=rd();\n\t\t\t\tADD(clr[x],dfn[x],0);\n\t\t\t\tADD(clr[x]=y,dfn[x],val[x]);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 'W':{\n\t\t\t\tx=rd(),y=rd();\n\t\t\t\tADD(clr[x],dfn[x],val[x]=y);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 'S':{\n\t\t\t\tx=rd(),y=rd();\n\t\t\t\tint RT=0;c=clr[x];\n\t\t\t\twhile(tp[x]!=tp[y]){\n\t\t\t\t\tif(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}\n\t\t\t\t\tRT+=qrySm(rt[c],dfn[tp[x]],dfn[x],1,n);\n\t\t\t\t\tx=fa[tp[x]];\n\t\t\t\t}\n\t\t\t\tif(dep[x]<dep[y]){Swap(x,y);}\n\t\t\t\tRT+=qrySm(rt[c],dfn[y],dfn[x],1,n);\n\t\t\t\tprintf(\"%d\\n\",RT);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 'M':{\n\t\t\t\tx=rd(),y=rd();\n\t\t\t\tint RT=0;c=clr[x];\n\t\t\t\twhile(tp[x]!=tp[y]){\n\t\t\t\t\tif(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}\n\t\t\t\t\tRT=Max(RT,qryMx(rt[c],dfn[tp[x]],dfn[x],1,n));\n\t\t\t\t\tx=fa[tp[x]];\n\t\t\t\t}\n\t\t\t\tif(dep[x]<dep[y]){Swap(x,y);}\n\t\t\t\tRT=Max(RT,qryMx(rt[c],dfn[y],dfn[x],1,n));\n\t\t\t\tprintf(\"%d\\n\",RT);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t}\n}\nint main(){\n\/\/\tfreopen(\"33132.in\",\"r\",stdin);\n\/\/\tfreopen(\"33132.ans\",\"w\",stdout);\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u867d\u7136\u8fd9\u4e00\u9898\u88ab\u5212\u5728\u4e3b\u5e2d\u6811\u4e0b\u9762\uff0c\u4f46\u662f\u4e00\u773c\u770b\u8fc7\u53bb\u8fd9\u4e0d\u5c31\u662f\u6811\u94fe\u5256\u5206\u52a8\u6001\u5f00\u70b9\u7ebf\u6bb5\u6811\u7684\u6a21\u677f\u9898\u4e48\u3002 \u6811\u94fe\u5256\u5206\u540e\u6211\u4eec\u8003\u8651\u5bf9\u6bcf\u4e00 … <\/p>\n