\u6811\u5256\u5957\u7ebf\u6bb5\u6811\u88f8\u9898\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)\nusing namespace std;\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}\nconst int N=30005;\nconst int INF=2147483647;\nstruct ee{\n\tint v;\n\tint nxt;\n}e[N<<1];\nint h[N],et=0;\ninline void add(int U,int V){\n\te[++et]=(ee){V,h[U]};\n\th[U]=et;\n}\nint dep[N],fa[N],sz[N],sn[N],tp[N],dfn[N];\nint val[N],n;\ninline void dfs0(int X,int FA){\n\tsz[X]=1,sn[X]=0;\n\tfa[X]=FA;dep[X]=dep[FA]+1;\n\tFv(i,X){\n\t\tif(e[i].v==FA){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs0(e[i].v,X);\n\t\tsz[X]+=sz[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}\n}\nint cnt=0;\ninline void dfs1(int X,int FA,int TP){\n\ttp[X]=TP;\n\tdfn[X]=++cnt;\n\tif(sn[X]){\n\t\tdfs1(sn[X],X,TP);\n\t}\n\tFv(i,X){\n\t\tif(e[i].v==FA||e[i].v==sn[X]){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs1(e[i].v,X,e[i].v);\n\t}\n}\n\n#define MID ((L+R)>>1)\n#define LS (X<<1)\n#define RS (X<<1|1)\nint tr[240005],mx[240005];\ninline void updt(int X){\n\ttr[X]=tr[LS]+tr[RS];\n\tmx[X]=Max(mx[LS],mx[RS]);\n}\ninline void chg(int X,int L,int R,int P,int V){\n\tif(L==R){\n\t\ttr[X]=mx[X]=V;\n\t\treturn;\n\t}\n\tP<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);\n\tupdt(X);\n\treturn;\n}\ninline int qrySm(int X,int L,int R,int A,int B){\n\tif(L>=A&&R<=B){\n\t\treturn tr[X];\n\t}\n\tif(R<A||L>B){\n\t\treturn 0;\n\t}\n\treturn qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);\n}\ninline int qryMx(int X,int L,int R,int A,int B){\n\tif(L>=A&&R<=B){\n\t\treturn mx[X];\n\t}\n\tif(R<A||L>B){\n\t\treturn -INF;\n\t}\n\treturn Max(qryMx(LS,L,MID,A,B),qryMx(RS,MID+1,R,A,B));\n}\n\nvoid init(){\n\tscanf(\"%d\",&n);\n\tint u,v;\n\tfor(int i=1;i<n;++i){\n\t\tscanf(\"%d%d\",&u,&v);\n\t\tadd(u,v),add(v,u);\n\t}\n\tsz[0]=0;\n\tdfs0(1,0);\n\tdfs1(1,0,1);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d\",&val[i]);\n\t\tchg(1,1,n,dfn[i],val[i]);\n\t}\n\tchar ch[6];\n\tint q,ans;\n\tscanf(\"%d\",&q);\n\tfor(int i=1;i<=q;++i){\n\t\tstd::cin>>ch+1;\n\t\tscanf(\"%d%d\",&u,&v);\n\t\tswitch(ch[2]){\n\t\t\tcase 'H':{\n\t\t\t\tval[u]=v;\n\t\t\t\tchg(1,1,n,dfn[u],v);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 'S':{\n\t\t\t\tans=0;\n\t\t\t\twhile(tp[u]!=tp[v]){\n\t\t\t\t\tif(dep[tp[u]]<dep[tp[v]]){\n\t\t\t\t\t\tSwap(u,v);\n\t\t\t\t\t}\n\t\t\t\t\tans+=qrySm(1,1,n,dfn[tp[u]],dfn[u]);\n\t\t\t\t\tu=fa[tp[u]];\n\t\t\t\t}\n\t\t\t\tif(dep[u]>dep[v]){\n\t\t\t\t\tSwap(u,v);\n\t\t\t\t}\n\t\t\t\tans+=qrySm(1,1,n,dfn[u],dfn[v]);\n\t\t\t\tprintf(\"%d\\n\",ans);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 'M':{\n\t\t\t\tans=-INF;\n\t\t\t\twhile(tp[u]!=tp[v]){\n\t\t\t\t\tif(dep[tp[u]]<dep[tp[v]]){\n\t\t\t\t\t\tSwap(u,v);\n\t\t\t\t\t}\n\t\t\t\t\tans=Max(ans,qryMx(1,1,n,dfn[tp[u]],dfn[u]));\n\t\t\t\t\tu=fa[tp[u]];\n\t\t\t\t}\n\t\t\t\tif(dep[u]>dep[v]){\n\t\t\t\t\tSwap(u,v);\n\t\t\t\t}\n\t\t\t\tans=Max(ans,qryMx(1,1,n,dfn[u],dfn[v]));\n\t\t\t\tprintf(\"%d\\n\",ans);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t}\n} \n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u6811\u5256\u5957\u7ebf\u6bb5\u6811\u88f8\u9898\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[30,43,56,70,9,6,48,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/872"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=872"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/872\/revisions"}],"predecessor-version":[{"id":873,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/872\/revisions\/873"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=872"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=872"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=872"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}