[ZJOI2015] 幻想乡战略游戏
程序员文章站
2022-07-11 11:18:25
令1为树根,T=Σd[i],sum[x]是子树x中的d之和,dis[x]是节点x的带权深度。 对于节点x的儿子y,边长为w,如果y比x更优,则(T sum[y])\ w sum[y]\ w=T/2。 换句话说,若存在sum[y] T/2,显然y更优,且y只存在一个(对于x);若存在sum[y]=T/ ......
令1为树根,t=σd[i],sum[x]是子树x中的d之和,dis[x]是节点x的带权深度。
对于节点x的儿子y,边长为w,如果y比x更优,则(t-sum[y])*w-sum[y]*w<=0即sum[y]>=t/2。
换句话说,若存在sum[y]>t/2,显然y更优,且y只存在一个(对于x);若存在sum[y]=t/2,(1个或2个),因为y的子树内都不存在sum>t/2的点,所以y就是一个最优解,不必递归地做。
考虑一类暴力求出最优点:从根出发依次进入sum>t/2的儿子,最深的那个点即为带权重心。这可以树剖维护sum/区间最大值,如果右半区间(较深)存在>=t/2,即向右跳转。
设已经求出了最优点r,答案是σ(d[i]*dis[i]+d[i]*dis[r]-2*d[i]*dis[lca(r,i)]),套路地维护就行了。
意外的简单?
#include <bits/stdc++.h> #define ll long long #define trvl(x,i,y) for(int i=ehd[x],y; y=to[i],i; i=lst[i]) #define ls (x<<1) #define rs (x<<1|1) using namespace std; const int n=1e5+10; int n,m; int ehd[n],to[n<<1],len[n<<1],lst[n<<1]; int fa[n],siz[n],son[n],top[n],id[n],dfn[n]; ll s,t,dis[n]; void insert(int x,int y,int w) { static int cnt=0; to[++cnt]=y,len[cnt]=w,lst[cnt]=ehd[x],ehd[x]=cnt; to[++cnt]=x,len[cnt]=w,lst[cnt]=ehd[y],ehd[y]=cnt; } void dfs1(int x,int p) { fa[x]=p; siz[x]=1; trvl(x,i,y) if(y!=p) { dis[y]=dis[x]+len[i]; dfs1(y,x);siz[x]+=siz[y]; if(siz[y]>siz[son[x]]) son[x]=y; } } void dfs2(int x,int t) { static int cnt=0; top[dfn[id[x]=++cnt]=x]=t; if(son[x]) dfs2(son[x],t); trvl(x,i,y) if(son[x]!=y&&fa[x]!=y) dfs2(y,y); } int tag[n<<2],mx[n<<2]; ll c[n<<2],s[n<<2]; void psd(int x) { if(!tag[x]) return; c[ls]+=s[ls]*tag[x],mx[ls]+=tag[x],tag[ls]+=tag[x]; c[rs]+=s[rs]*tag[x],mx[rs]+=tag[x],tag[rs]+=tag[x]; tag[x]=0; } void upd(int x) { mx[x]=max(mx[ls],mx[rs]); c[x]=c[ls]+c[rs]; } void build(int x,int l,int r) { if(l==r) { s[x]=dis[dfn[l]]-dis[fa[dfn[l]]]; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); s[x]=s[ls]+s[rs]; } int find(int x,int l,int r) { if(l==r) return dfn[l]; int mid=(l+r)>>1; psd(x); if(mx[rs]*2>t) return find(rs,mid+1,r); return find(ls,l,mid); } void mdf(int x,int l,int r,int l,int r,ll w) { if(l<=l&&r<=r) { c[x]+=s[x]*w,mx[x]+=w,tag[x]+=w; return; } int mid=(l+r)>>1; psd(x); if(l<=mid) mdf(ls,l,mid,l,r,w); if(mid<r) mdf(rs,mid+1,r,l,r,w); upd(x); } ll qry(int x,int l,int r,int l,int r) { if(l<=l&&r<=r) return c[x]; int mid=(l+r)>>1; ll c=0; psd(x); if(l<=mid) c+=qry(ls,l,mid,l,r); if(mid<r) c+=qry(rs,mid+1,r,l,r); return c; } void modify(int x,int w) { for(; x; x=fa[top[x]]) mdf(1,1,n,id[top[x]],id[x],w); } ll query(int x,ll w=0) { for(; x; x=fa[top[x]]) w+=qry(1,1,n,id[top[x]],id[x]); return w; } int main() { scanf("%d%d",&n,&m); for(int x,y,w,i=n; --i; ) { scanf("%d%d%d",&x,&y,&w); insert(x,y,w); } dfs1(1,0); dfs2(1,1); build(1,1,n); for(int x,w; m--; ) { scanf("%d%d",&x,&w); modify(x,w); s+=dis[x]*w; t+=w; x=find(1,1,n); printf("%lld\n",s+t*dis[x]-2*query(x)); } return 0; }