\u4ed4\u7ec6\u8003\u8651\u8fd9\u9053\u9898\uff0c\u6211\u4eec\u53ef\u4ee5\u5c06\u95ee\u9898\u8f6c\u5316\u4e3a\u300c\u4fee\u6539\u300d\u548c\u300c\u6362\u6839\u300d\u4e24\u4e2a\u64cd\u4f5c\u3002
\u5bf9\u4e8e\u4fee\u6539\u64cd\u4f5c\uff0c\u6211\u4eec\u77e5\u9053\uff0c\u6bcf\u4e2a\u70b9\u7684\u6743\u503c\u5bf9\u4e14\u4ec5\u5bf9\u5b83\u5230\u6839\u8282\u70b9\u4e0a\u7684\u8fd9\u4e00\u6761\u94fe\u4e0a\u7684\u6bcf\u4e2a\u70b9\u7684\u7b54\u6848\u4ea7\u751f\u8d21\u732e\u3002
\u6211\u4eec\u4e0d\u59a8\u4ee4\u4ee51\u4e3a\u6839\u7684\u60c5\u51b5\u4e0b\u7684\u6bcf\u4e2a\u70b9\u7684\u4fee\u6539\u524d\u5b50\u6811\u6743\u503c\u548c\u4e3a\\(a_{i}\\)\uff0c\u4fee\u6539\u5bf9\u6743\u503c\u7684\u6539\u53d8\u4e3a\\(dlt\\)\uff0c\u90a3\u4e48\u53ef\u4ee5\u8ba1\u7b97\u5f97\uff1a
$$ans’=\\sum(a_{i}+dlt)^2=\\sum a_{i}^2+2dlt\\times a_{i}+dlt^2\\times len$$
\u6545\u800c\uff0c\u6211\u4eec\u53ea\u9700\u8981\u7528\u6811\u94fe\u5256\u5206\u5957\u7ebf\u6bb5\u6811\u7ef4\u62a4\u6811\u4e0a\u533a\u95f4\u5e73\u65b9\u548c\u5373\u53ef\u3002<\/p>\n\n\n\n
\u63a5\u4e0b\u6765\u6211\u4eec\u8003\u8651\u6362\u6839\u64cd\u4f5c\u3002
\n\u6211\u4eec\u5047\u8bbe\u6839\u4ece1\u6362\u5230\u4e86\\(x\\)\uff0c\u90a3\u4e48\u5b50\u6811\u6743\u503c\u5927\u5c0f\u4f1a\u53d1\u751f\u6539\u53d8\u7684\u4ec5\u6709\u8fd9\u6761\u8def\u5f84\u7ecf\u8fc7\u7684\u70b9\u3002\u6211\u4eec\u4e0d\u59a8\u4ee4\u6362\u6839\u540e\u5b83\u4eec\u7684\u5b50\u6811\u6743\u503c\u548c\u4e3a\\(b_{i}\\)\uff0c\u5e76\u67091~x\u4e3a\u8fd9\u6761\u8def\u5f84\u6784\u6210\u7684\u5e8f\u5217\uff0c\u5219\u6211\u4eec\u53d1\u73b0\u7b54\u6848\u4f1a\u505a\u51fa\u5982\u4e0b\u53d8\u52a8\uff1a
\n$$ans’=ans-\\sum_{i=x}^1 a_{i}^2+\\sum_{i=x}^1 b_{i}^2$$
\n\u6211\u4eec\u53d1\u73b0\uff0c\u8def\u5f84\u4e0a\u7684\u76f8\u90bb\u70b9\u7684\u5b50\u6811\u7684\u5e76\u96c6\u6784\u6210\u4e86\u6574\u68f5\u6811\u3002\u8fd9\u4e5f\u5c31\u610f\u5473\u7740\uff1a
\n$$a_{i}+b_{i+1}=a_{0}=b_{x}$$
\n\u4e8e\u662f\u6211\u4eec\u53ef\u4ee5\u4f9d\u6b64\u5f97\u5230\uff1a
\n$$ans’=ans-\\sum_{i=x}^1 a_{i}^2+b_x^2+\\sum_{i=x-1}^1 (a_{0}-a_{i+1})^2$$
\n$$ans’=ans-\\sum_{i=x}^2 a_{i}^2+(len-1)\\times a_{0}^2-2a_{0}\\times\\sum_{i=x-1}^1 a_{i+1}+\\sum_{i=x}^2a_{i}^2$$
\n$$ans’=(len-1)a_0^2-2a_{0}\\sum_{i=x}^2a_{i}$$
\n\u540c\u6837\u4e5f\u53ef\u4ee5\u7528\u6811\u94fe\u5256\u5206\u5957\u7ebf\u6bb5\u6811\u7ef4\u62a4\u6811\u4e0a\u533a\u95f4\u548c\u4e0e\u533a\u95f4\u5e73\u65b9\u548c\u3002
\n\u6ce8\u610f\uff1a\u6811\u5256\u4e0d\u8981\u5199\u6302\uff0c\u4e0b\u4f20\u7ed9\u91cd\u513f\u5b50\u7684\u94fe\u9876\u5e94\u8be5\u662f\u672c\u8282\u70b9\u7684\u94fe\u9876\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#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)\ntypedef long long ll;\n\ninline char rdc() {\n \tstatic char buf[10000000], *p = buf, *end = buf;\n\tif (p == end) end = buf + fread(p = buf, sizeof(char), 10000000, stdin);\n\treturn *(p++);\n}\n\ninline int rd(){\n\tint RT=0,c,f=1;\n\twhile(!isdigit(c=rdc())){if(c=='-'){f=-1;}}\n\tdo{RT=RT*10+c-'0';}while(isdigit(c=rdc()));\n\treturn RT*f;\n}\n\nstruct ee{\n\tint v;\n\tint nxt;\n}e[400005];\nint h[200005],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);\n\tEadd(V,U);\n}\n\nint n,q;\nll val[200005],sm[200005];\nint fa[200005],dep[200005],tp[200005],sn[200005],sz[200005];\nint dfn[200005],loc[200005],cnt=0;\n\ninline void dfs0(int X,int FA){\n\tdep[X]=dep[FA]+1;\n\tfa[X]=FA;\n\tsz[X]=1;\n\tsm[X]=val[X];\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\tsm[X]+=sm[e[i].v];\n\t}\n}\n\ninline void dfs1(int X,int TP){\n\tloc[dfn[X]=++cnt]=X;\n\ttp[X]=TP;\n\tif(sn[X]){\n\t\tdfs1(sn[X],TP);\n\t\t\/\/\u8fd9\u91cc\u4e0b\u4f20\u7684\u5e94\u8be5\u662fTP\u800c\u975eX...\n\t\t\/\/\u6811\u5256\u5199\u6302\u4e86\uff0c\u6211SB \n\t}\n\tFv(i,X){\n\t\tif(e[i].v==fa[X]||e[i].v==sn[X]){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs1(e[i].v,e[i].v);\n\t}\n}\n#define MID ((L+R)>>1)\n#define LS (X<<1)\n#define RS (X<<1|1)\n#define LEN (R-L+1)\n#define LLEN (MID-L+1)\n#define RLEN (R-MID)\nstruct data{\n\tll sm;\n\tll sm2;\n\tll lzy;\n}tr[2000005];\n\ninline void rnw(int X,int Len,ll K){\n\ttr[X].sm2+=(K*K*Len+tr[X].sm*K*2);\n\ttr[X].sm+=(Len*K);\n\ttr[X].lzy+=K;\n}\ninline void pshd(int X,int L,int R){\n\trnw(LS,LLEN,tr[X].lzy),rnw(RS,RLEN,tr[X].lzy);\n\ttr[X].lzy=0;\n}\ninline void updt(int X){\n\ttr[X].sm=tr[LS].sm+tr[RS].sm;\n\ttr[X].sm2=tr[LS].sm2+tr[RS].sm2;\n}\ninline void chg(int X,int L,int R,int A,int B,int V){\n\tif(L>=A&&R<=B){\n\t\trnw(X,LEN,V);\n\t\treturn;\n\t}\n\tpshd(X,L,R);\n\tif(A<=MID){\n\t\tchg(LS,L,MID,A,B,V);\n\t}\n\tif(B>MID){\n\t\tchg(RS,MID+1,R,A,B,V);\n\t}\n\tupdt(X);\n}\ninline ll qrySm(int X,int L,int R,int A,int B){\n\tif(L>=A&&R<=B){\n\t\treturn tr[X].sm;\n\t}\n\tif(L>B||R<A||B<A){\n\t\treturn 0;\n\t}\n\tpshd(X,L,R);\n\treturn qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);\n}\ninline ll qrySm2(int X,int L,int R,int A,int B){\n\tif(L>=A&&R<=B){\n\t\treturn tr[X].sm2;\n\t}\n\tif(L>B||R<A||B<A){\n\t\treturn 0;\n\t}\n\tpshd(X,L,R);\n\treturn qrySm2(LS,L,MID,A,B)+qrySm2(RS,MID+1,R,A,B);\n}\ninline void build(int X,int L,int R){\n\tif(L==R){\n\t\ttr[X].sm=sm[loc[L]];\n\t\ttr[X].sm2=tr[X].sm*tr[X].sm;\n\t\treturn;\n\t}\n\tbuild(LS,L,MID);build(RS,MID+1,R);\n\tupdt(X);\n}\n\nvoid init(){\n\tn=rd(),q=rd();\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\tfor(int i=1;i<=n;++i){\n\t\tval[i]=rd();\n\t}\n\tdfs0(1,0);\n\tdfs1(1,1);\n\tbuild(1,1,n);\n\tint op,x,y;\n\tll ans,a0=sm[1],sma,len;\n\tfor(int i=1;i<=q;++i){\n\t\top=rd();\n\t\tif(op==1){\n\t\t\tx=rd(),y=rd();\n\t\t\ty-=val[x];\n\t\t\tval[x]+=y;\n\t\t\ta0+=y;\n\t\t\twhile(x){\n\t\t\t\tchg(1,1,n,dfn[tp[x]],dfn[x],y);\n\t\t\t\tx=fa[tp[x]];\n\t\t\t}\n\t\t}else{\n\t\t\tx=rd();\n\t\t\tlen=sma=ans=0;\n\t\t\tans=qrySm2(1,1,n,1,n);\n\t\t\twhile(tp[x]!=tp[1]){\n\t\t\t\tlen+=dfn[x]-dfn[tp[x]]+1;\n\t\t\t\tsma+=qrySm(1,1,n,dfn[tp[x]],dfn[x]);\n\t\t\t\tx=fa[tp[x]];\n\t\t\t}\n\t\t\tlen+=dfn[x]-dfn[1];\n\t\t\tsma+=qrySm(1,1,n,dfn[1]+1,dfn[x]);\n\t\t\tprintf(\"%lld\\n\",ans+a0*(len*a0-2*sma));\n\t\t}\n\t}\n}\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4ed4\u7ec6\u8003\u8651\u8fd9\u9053\u9898\uff0c\u6211\u4eec\u53ef\u4ee5\u5c06\u95ee\u9898\u8f6c\u5316\u4e3a\u300c\u4fee\u6539\u300d\u548c\u300c\u6362\u6839\u300d\u4e24\u4e2a\u64cd\u4f5c\u3002 \u5bf9\u4e8e\u4fee\u6539\u64cd\u4f5c\uff0c\u6211\u4eec\u77e5\u9053\uff0c\u6bcf\u4e2a\u70b9\u7684\u6743\u503c\u5bf9\u4e14\u4ec5\u5bf9 … <\/p>\n