\u7136\u540e\u5c31\u662f\u5982\u4f55\u627e\u5230\u60c5\u51b53\u7684\u70b9\uff0c\u6211\u4eec\u53ef\u4ee5\u5728\u6bcf\u6761\u91cd\u94fe\u7684\u7ebf\u6bb5\u6811\u4e2d\u4e8c\u5206\uff0c\u627e\u5230\u7b2c\u4e00\u4e2amn\u503c\u5c0f\u4e8ev\u7684\u70b9<\/p>\n
\u9700\u8981\u6ce8\u610f\u7684\u662f\u7ebf\u6bb5\u6811\u6309dfs\u5e8f\u5b58\u50a8\uff0c\u6240\u4ee5\u9760\u53f3\u7684\u70b9\u66f4\u63a5\u8fd1\u5f53\u524d\u70b9\uff0c\u6240\u4ee5\u6211\u4eec\u5e94\u8be5\u5148\u5728\u53f3\u4fa7\u5bfb\u627e<\/p>\n
\u7136\u540e\uff0c\u5c31\u4e00\u76f4\u5faa\u73af\uff0c\u76f4\u5230\u51fa\u73b0\u60c5\u51b51\u6216\u8005\u5230\u6839\u8282\u70b9<\/p>\n<\/div>\n<\/div>\n
\n
#include<map>\r\n#include<cmath>\r\n#include<queue>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<iostream>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define inf 1000000007\r\n#define ll long long\r\n#define N 200010\r\ninline int rd()\r\n{\r\n\tint x=0,f=1;char ch=getchar();\r\n\twhile(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}\r\n\twhile(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}\r\n\treturn x*f;\r\n}\r\nint lj[N],fro[N<<1],to[N<<1],cnt;\r\nvoid add(int a,int b){fro[++cnt]=lj[a];to[cnt]=b;lj[a]=cnt;}\r\nint n,T;\r\nll w[N];\r\nint fa[N],son[N],sz[N],top[N],tid[N],tim,rk[N];\r\nll h[N],dp[N];\r\nvoid dfs1(int x,int f)\r\n{\r\n\tfa[x]=f;sz[x]=1;\r\n\tfor(int i=lj[x];i;i=fro[i])\r\n\t{\r\n\t\tif(to[i]==f) continue;\r\n\t\tdfs1(to[i],x);\r\n\t\th[x]+=dp[to[i]];sz[x]+=sz[to[i]];\r\n\t\tif(sz[son[x]]<sz[to[i]]) son[x]=to[i];\r\n\t}\r\n\tif(!son[x]) h[x]=inf;\r\n\tdp[x]=min(w[x],h[x]);\r\n}\r\nvoid dfs2(int x,int tp)\r\n{\r\n\ttid[x]=++tim;\r\n\trk[tim]=x;top[x]=tp;\r\n\tif(!son[x]) return;\r\n\tdfs2(son[x],tp);\r\n\tfor(int i=lj[x];i;i=fro[i])\r\n\t{\r\n\t\tif(to[i]==son[x]||to[i]==fa[x]) continue;\r\n\t\tdfs2(to[i],to[i]);\r\n\t}\r\n}\r\n#define ls p<<1\r\n#define rs p<<1|1\r\nll mn[N<<2],tg[N<<2];\r\nvoid build(int p,int l,int r)\r\n{\r\n\tif(l==r){mn[p]=w[rk[l]]-h[rk[l]];tg[p]=h[rk[l]];return;}\r\n\tint mid=l+r>>1;\r\n\tbuild(ls,l,mid);\r\n\tbuild(rs,mid+1,r);\r\n\tmn[p]=min(mn[ls],mn[rs]);\r\n}\r\ninline void pd(int p)\r\n{\r\n\tif(!tg[p]) return;\r\n\tmn[ls]-=tg[p];mn[rs]-=tg[p];\r\n\ttg[ls]+=tg[p];tg[rs]+=tg[p];\r\n\ttg[p]=0;\r\n}\r\nll fd(int p,int l,int r,int x)\r\n{\r\n\tif(l==r) return tg[p];\r\n\tpd(p);\r\n\tint mid=l+r>>1;\r\n\treturn x<=mid?fd(ls,l,mid,x):fd(rs,mid+1,r,x);\r\n}\r\nll ask(int x){return min(w[x],fd(1,1,n,tid[x]));}\r\nvoid xg(int p,int l,int r,int x)\r\n{\r\n\tif(l==r){mn[p]=w[rk[l]]-tg[p];return;}\r\n\tint mid=l+r>>1;\r\n\tif(x<=mid) xg(ls,l,mid,x);\r\n\telse xg(rs,mid+1,r,x);\r\n\tmn[p]=min(mn[ls],mn[rs]);\r\n}\r\nvoid xg(int p,int l,int r,int L,int R,ll v)\r\n{\r\n\tif(l==L&&R==r){mn[p]-=v;tg[p]+=v;return;}\r\n\tpd(p);\r\n\tint mid=l+r>>1;\r\n\tif(R<=mid) xg(ls,l,mid,L,R,v);\r\n\telse if(L>mid) xg(rs,mid+1,r,L,R,v);\r\n\telse xg(ls,l,mid,L,mid,v),xg(rs,mid+1,r,mid+1,R,v);\r\n\tmn[p]=min(mn[ls],mn[rs]);\r\n}\r\nvoid chg(int x,int y,ll v)\r\n{\r\n\twhile(top[x]!=top[y]) xg(1,1,n,tid[top[x]],tid[x],v),x=fa[top[x]];\r\n\txg(1,1,n,tid[y],tid[x],v);\r\n}\r\nint fd(int p,int l,int r,int L,int R,ll v)\r\n{\r\n\tif(L<=l&&r<=R)\r\n\t{\r\n\t\tif(mn[p]>=v) return l;\r\n\t\tif(l==r) return 0;\r\n\t}\r\n\tpd(p);\r\n\tint mid=l+r>>1,tp;\r\n\tif(R<=mid) return fd(ls,l,mid,L,R,v);\r\n\tif(L>mid) return fd(rs,mid+1,r,L,R,v);\r\n\ttp=fd(rs,mid+1,r,L,R,v);\r\n\tif(!tp||tp>mid+1) return tp;\r\n\ttp=fd(ls,l,mid,L,R,v);\r\n\treturn tp?tp:mid+1;\r\n}\r\nint gety(int x,ll v)\r\n{\r\n\tint t=x,tp;x=fa[x];\r\n\twhile(x)\r\n\t{\r\n\t\ttp=fd(1,1,n,tid[top[x]],tid[x],v);\r\n\t\tif(!tp) break;\r\n\t\tif(tp>tid[top[x]]) return rk[tp];\r\n\t\tt=top[x];x=fa[t]; \r\n\t}\r\n\treturn t;\r\n}\r\nvoid cg(int x,ll v)\r\n{\r\n\tint tp=ask(x);\r\n\tll d;\r\n\tw[x]+=v;\r\n\txg(1,1,n,tid[x]);\r\n\td=ask(x)-tp;\r\n\tif(!d) return;\r\n\twhile(fa[x])\r\n\t{\r\n\t\tint y=gety(x,d);\r\n\t\tif(x!=y) chg(fa[x],y,d);\r\n\t\tx=fa[y];\r\n\t\tif(!x) return;\r\n\t\ttp=ask(x);\r\n\t\tchg(x,x,d);\r\n\t\td=ask(x)-tp;\r\n\t\tif(!d) return;\r\n\t}\r\n}\r\nint main()\r\n{\r\n\tn=rd();\r\n\tfor(int i=1;i<=n;i++) w[i]=rd();\r\n\tint x,y;\r\n\tfor(int i=1;i<n;i++)\r\n\t{\r\n\t\tx=rd();y=rd();\r\n\t\tadd(x,y);add(y,x);\r\n\t}\r\n\tdfs1(1,0);dfs2(1,1);\r\n\tbuild(1,1,n);\r\n\tT=rd();\r\n\tchar op[2];\r\n\twhile(T--)\r\n\t{\r\n\t\tscanf(\"%s\",op);x=rd();\r\n\t\tif(op[0]=='Q') printf(\"%lld\\n\",ask(x));\r\n\t\telse{y=rd();cg(x,y);}\r\n\t}\r\n\treturn 0;\r\n}\r\n<\/pre>\n <\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
4712: \u6d2a\u6c34 Time Limit:\u00a015 Sec\u00a0\u00a0Memory Limit:\u00a0256 M […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[5,33],"class_list":["post-420","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-dp","tag-33"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/420","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=420"}],"version-history":[{"count":3,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/420\/revisions"}],"predecessor-version":[{"id":423,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/420\/revisions\/423"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=420"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=420"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=420"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}