\u8003\u8651\u8fd9\u4e00\u9898\u5728\u94fe\u4e0a\u7684\u60c5\u51b5\u3002
\n\u663e\u7136\uff0c\u53ef\u4ee5\u5efa\u4e00\u68f5\u7ebf\u6bb5\u6811\uff0c\u4fee\u6539\u662f\u6253\u6807\u8bb0\u4e0b\u4f20\uff0c\u67e5\u8be2\u662f\u5de6\u53f3\u76f8\u52a0\u7279\u5224\u5de6\u53f3\u76f8\u90bb\u5904\u989c\u8272\u662f\u5426\u76f8\u540c\u3002
\n\u770b\u8d77\u6765\u5728\u6811\u4e0a\u4e5f\u53ef\u4ee5\u8fd9\u4e48\u505a\u3002\u4f46\u662f\u4ed4\u7ec6\u60f3\u60f3\u4f1a\u53d1\u73b0\u4e0d\u592a\u5bf9\u3002
\n\u8fd9\u662f\u56e0\u4e3a\uff0c\u6839\u636e\u6811\u94fe\u5256\u5206\u7684\u539f\u7406\uff0c\u6bcf\u4e24\u6761\u5256\u5f00\u7684\u94fe\u662f\u72ec\u7acb\u67e5\u8be2\u7684\u3002
\n\u56e0\u6b64\uff0c\u5728\u6811\u4e0a\u67e5\u8be2\u7684\u65f6\u5019\uff0c\u9700\u8981\u989d\u5916\u67e5\u8be2\u4e24\u4e2a\u76f8\u63a5\u7684\u94fe\u7684\u63a5\u9a73\u5904\u7684\u989c\u8272\u662f\u5426\u76f8\u540c\u3002
\n\u8fd9\u5927\u6982\u5c31\u505a\u5b8c\u4e86\u3002 <\/p>\n\n\n\n
\u7136\u540e\u6211\u4eec\u53d1\u73b0\u5b9e\u65f6\u67e5\u8be2\u63a5\u9a73\u5904\u7684\u989c\u8272\u4e0d\u4ec5\u5f88\u50bb\uff0c\u800c\u4e14\u5bb9\u6613\u9519\u3002
\n\u6240\u4ee5\u6211\u4eec\u8003\u8651\u5f00\u4e24\u4e2a\u6570\u7ec4\uff1alc\u548crc\uff0c\u50a8\u5b58\u4e00\u4e2a\u533a\u95f4\u5185\u5de6\u7aef\u989c\u8272\u548c\u53f3\u7aef\u989c\u8272\u3002 <\/p>\n\n\n\n
\u53e6\u5916\u5c31\u662f\u94fe\u4e0a\u63a5\u9a73\u5904\u7684\u989c\u8272\u95ee\u9898\u3002\u4e00\u79cd\u5bb9\u6613\u60f3\u5230\u7684\u65b9\u6cd5\u662f\u6bcf\u4e00\u6b21\u8bb0\u5f55\u5b83\u6765\u7684\u90a3\u4e2a\u70b9\uff0c\u7136\u540e\u6bd4\u8f83\u6765\u7684\u90a3\u4e2a\u70b9\u548c\u81ea\u8eab\u3002
\n\u7136\u800c\u8fd9\u4e48\u505a\u540c\u6837\u662f\u4e0d\u4ec5\u50bb\u800c\u4e14\u5bb9\u6613\u9519\u7684\u3002\u4e8e\u662f\u6211\u4eec\u8003\u8651\u53e6\u4e00\u79cd\u65b9\u6cd5\uff1a\u6bcf\u4e00\u6b21\u6bd4\u8f83\u94fe\u9876\u548c\u94fe\u9876\u7684\u7236\u4eb2\u8fd9\u4e24\u4e2a\u70b9\uff0c\u5e76\u5c06\u5b83\u7684\u8d1f\u8d21\u732e\u9884\u5148\u6263\u9664\u3002\u8fd9\u6837\u53ef\u4ee5\u6709\u6548\u7b80\u5316\u4ee3\u7801\u3002 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)\n\ninline void Swap(int &A,int &B){\n A^=B^=A^=B;\n}\nint n,m;\nconst int N=100005;\nstruct ee{\n int v;\n int nxt;\n}e[N<<1];\nint h[N],et=0;\ninline void Eadd(int U,int V){\n e[++et]=(ee){V,h[U]};\n h[U]=et;\n} \ninline void add(int U,int V){\n Eadd(U,V);\n Eadd(V,U);\n}\nint sn[N],sz[N],fa[N],dep[N];\ninline void dfs0(int X,int FA){\n fa[X]=FA;sz[X]=1;dep[X]=dep[FA]+1;sn[X]=0;\n Fv(i,X){\n if(e[i].v==FA){\n continue;\n }\n dfs0(e[i].v,X);\n if(sz[e[i].v]>sz[sn[X]]){\n sn[X]=e[i].v;\n }\n sz[X]+=sz[e[i].v];\n }\n}\nint dfn[N],tp[N],cnt=0;\ninline void dfs1(int X,int FA,int TP){\n dfn[X]=++cnt;tp[X]=TP;\n if(sn[X]){\n dfs1(sn[X],X,TP);\n }\n Fv(i,X){\n if(e[i].v==FA||e[i].v==sn[X]){\n continue;\n }\n dfs1(e[i].v,X,e[i].v);\n }\n}\nint clr[N];\n#define MID ((L+R)>>1)\n#define LS (X<<1)\n#define RS (X<<1|1)\nint tr[N<<2],tg[N<<2],val[N<<2],lc[N<<2],rc[N<<2];\ninline void mdf(int X,int C){\n tr[X]=tg[X]=lc[X]=rc[X]=C;\n val[X]=1;\n}\ninline void pshd(int X,int L,int R){\n\tif(L==R){\n\t\treturn;\n\t}\n if(tg[X]){\n mdf(LS,tg[X]),mdf(RS,tg[X]);\n tg[X]=0;\n }\n}\ninline int qryc(int X,int L,int R,int P){\n if(L==R){\n return tr[X];\n }\n pshd(X,L,R);\n return P<=MID?qryc(LS,L,MID,P):qryc(RS,MID+1,R,P);\n}\ninline void updt(int X,int L,int R){\n val[X]=(val[LS]+val[RS]-(rc[LS]==lc[RS]));\n lc[X]=lc[LS],rc[X]=rc[RS];\n}\ninline void chg(int X,int L,int R,int A,int B,int C){\n if(A<=L&&R<=B){\n mdf(X,C);\n return;\n }\n if(L>B||R<A){\n return;\n }\n pshd(X,L,R);\n chg(LS,L,MID,A,B,C);chg(RS,MID+1,R,A,B,C);\n updt(X,L,R);\n}\ninline int qryv(int X,int L,int R,int A,int B){\n if(A<=L&&R<=B){\n return val[X];\n }\n if(L>B||R<A){\n return 0;\n }\n pshd(X,L,R);\n return qryv(LS,L,MID,A,B)+qryv(RS,MID+1,R,A,B)-((A<=MID&&B>MID)?(rc[LS]==lc[RS]):0);\n}\nvoid init(){\n scanf(\"%d%d\",&n,&m);\n for(int i=1;i<=n;++i){\n scanf(\"%d\",&clr[i]);\n }\n int u,v;\n for(int i=1;i<n;++i){\n scanf(\"%d%d\",&u,&v);\n add(u,v);\n }\n sz[0]=0,dep[0]=0;\n dfs0(1,0);\n dfs1(1,0,1);\n for(int i=1;i<=n;++i){\n chg(1,1,n,dfn[i],dfn[i],clr[i]);\n }\n char ch[4];\n int c,ans;\n for(int i=1;i<=m;++i){\n std::cin>>ch+1;\n switch(ch[1]){\n case 'Q':{\n scanf(\"%d%d\",&u,&v);\n ans=0;\n while(tp[u]!=tp[v]){\n if(dep[tp[u]]<dep[tp[v]]){\n Swap(u,v);\n }\n ans+=qryv(1,1,n,dfn[tp[u]],dfn[u]);\n ans-=(qryc(1,1,n,dfn[tp[u]])==qryc(1,1,n,dfn[fa[tp[u]]]));\n u=fa[tp[u]];\n }\n if(dep[u]<dep[v]){\n Swap(u,v);\n }\n ans+=qryv(1,1,n,dfn[v],dfn[u]);\n printf(\"%d\\n\",ans);\n break;\n }\n case 'C':{\n scanf(\"%d%d%d\",&u,&v,&c);\n while(tp[u]!=tp[v]){\n if(dep[tp[u]]<dep[tp[v]]){\n Swap(u,v);\n }\n chg(1,1,n,dfn[tp[u]],dfn[u],c);\n u=fa[tp[u]];\n }\n if(dep[u]<dep[v]){\n Swap(u,v);\n }\n chg(1,1,n,dfn[v],dfn[u],c);\n break;\n }\n }\n }\n}\n\nint main(){\n init();\n return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u8003\u8651\u8fd9\u4e00\u9898\u5728\u94fe\u4e0a\u7684\u60c5\u51b5\u3002 \u663e\u7136\uff0c\u53ef\u4ee5\u5efa\u4e00\u68f5\u7ebf\u6bb5\u6811\uff0c\u4fee\u6539\u662f\u6253\u6807\u8bb0\u4e0b\u4f20\uff0c\u67e5\u8be2\u662f\u5de6\u53f3\u76f8\u52a0\u7279\u5224\u5de6\u53f3\u76f8\u90bb\u5904\u989c\u8272\u662f\u5426\u76f8\u540c\u3002 … <\/p>\n