傲嬌少女幽香正在玩一個非常有趣的戰略類游戲，本來這個游戲的地圖其實還不算太大，幽香還能管得過來，但是不知道為什么現在的網游廠商把游戲的地圖越做越大，以至于幽香一眼根本看不過來，更別說和別人打仗了。 在打仗之前，幽香現在面臨一個非常基本的管理問題需要解決。 整個地圖是一個樹結構，一共有n塊空地，這些空地被n-1條帶權邊連接起來，使得每兩個點之間有一條唯一的路徑將它們連接起來。在游戲中，幽香可能在空地上增加或者減少一些軍隊。同時，幽香可以在一個空地上放置一個補給站。 如果補給站在點u上，并且空地v上有dv個單位的軍隊，那么幽香每天就要花費dv×dist(u,v)的金錢來補給這些軍隊。由于幽香需要補給所有的軍隊，因此幽香總共就要花費為Sigma(Dv*dist(u，v),其中1<=V<=N)的代價。其中dist(u,v)表示u個v在樹上的距離（唯一路徑的權和）。 因為游戲的規定，幽香只能選擇一個空地作為補給站。在游戲的過程中，幽香可能會在某些空地上制造一些軍隊，也可能會減少某些空地上的軍隊，進行了這樣的操作以后，出于經濟上的考慮，幽香往往可以移動他的補給站從而省一些錢。但是由于這個游戲的地圖是在太大了，幽香無法輕易的進行最優的安排，你能幫幫她嗎？ 你可以假定一開始所有空地上都沒有軍隊。
第一行兩個數n和Q分別表示樹的點數和幽香操作的個數，其中點從1到n標號。 接下來n-1行，每行三個正整數a,b,c，表示a和b之間有一條邊權為c的邊。 接下來Q行，每行兩個數u,e，表示幽香在點u上放了e單位個軍隊（如果e<0，就相當于是幽香在u上減少了|e|單位個軍隊，說白了就是du←du+e）。數據保證任何時刻每個點上的軍隊數量都是非負的。
對于幽香的每個操作，輸出操作完成以后，每天的最小花費，也即如果幽香選擇最優的補給點進行補給時的花費。
題解：樹鏈剖分
這道題應該是動態點分治，但是也可以用樹鏈剖分來做，只不過比較麻煩。。。。
先考慮如何找到最優的位置。
應該是郵局選址問題，找到第一個大于等于總軍隊數一半的位置就是最合適的位置。從這個位置往任意方向移動，答案都不會變小。對應到樹上就是，找到深度最深的大于等于總軍隊數一半的節點。這個可以鏈剖后用線段樹維護。每次一個點的軍隊數量修改，該點到根路徑上所有點的權值都進行修改。在查詢的時候，因為鏈剖得到的dfs序中深度較深的節點在較靠后的位置，所有每次將對應的區間分成[l,mid],[mid+1,r]只要[mid+1,r]區間的最大值滿足條件就跳轉到[mid+1,r]這個區間，直到找到一個點為止。
考慮如何計算第二問的答案。
我們先定義幾個量，dis[i]表示點i到根的距離，loc表示第一位選取的位置，sum[i]表示點i的子樹中軍隊的個數。
ans=sigma sum[i]*dis[i]+ sigma sum[i]*dis[loc] -2*sigma sum[i]*dis[lca(loc,i)]
答案可以分成三部分，第二部分可以直接計算求解,第一部分用線段樹維護區間和，每次修改的時候只需要對于需要修改的點進行單點修改。
關鍵是第三部分如何求解，對于每個點我們都只會有一個重兒子，而每次查詢的時候走的都是重鏈。考慮lca(loc,i)的取值，只可能是loc到根路徑上的點，如果我們能計算出每個點的貢獻，那么問題就迎刃而解了。
我們對于每個點，維護該點子樹中的點(除去重兒子子樹中的點)的sum[i]*dis的值，那么如果loc在重兒子的子樹中，該點記錄的這個值就是以該點為lca的貢獻值。因為我們在向上走的過程中需要從一個重鏈跳到另一個重鏈，而走的這條邊是輕邊，這個特殊點需要單獨計算。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 100003#define LL long long using namespace std; int tot,n,m,sz,sig,point[N],nxt[N*2],v[N*2],len[N*2];LL tr[N*4],val[N*4],sum[N*4],d[N*4],delta[N*4],dis[N];int belong[N],q[N],pos[N],deep[N],size[N*4],fa[N],son[N];struct data{ LL sum,val;};void add(int x,int y,int z){ tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; len[tot]=z; tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; len[tot]=z;// cout<<x<<" "<<y<<" "<<z<<endl;}void dfs(int x,int f){ deep[x]=deep[f]+1; size[x]=1; for (int i=point[x];i;i=nxt[i]){ if (v[i]==f) continue; fa[v[i]]=x; dis[v[i]]=dis[x]+(LL)len[i]; dfs(v[i],x); size[x]+=size[v[i]]; if (size[v[i]]>size[son[x]]) son[x]=v[i]; }}void dfs1(int x,int chain){ belong[x]=chain; pos[x]=++sz; q[sz]=x; if (!son[x]) return; dfs1(son[x],chain); for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa[x]&&v[i]!=son[x]) dfs1(v[i],v[i]);}void update(int now){ if (sum[now<<1]>sum[now<<1|1]) sum[now]=sum[now<<1]; else sum[now]=sum[now<<1|1]; val[now]=val[now<<1]+val[now<<1|1]; tr[now]=tr[now<<1]+tr[now<<1|1]; d[now]=d[now<<1]+d[now<<1|1];}void build(int now,int l,int r){ if (l==r) { val[now]=0; d[now]=dis[q[l]]; //val表示lca為該點，輕邊相連的子樹與重兒子之間對答案的貢獻 sum[now]=0; tr[now]=0; //size[now]=0; return; } int mid=(l+r)/2; build(now<<1,l,mid); build(now<<1|1,mid+1,r); update(now);}void pushdown(int now){ if (delta[now]) { delta[now<<1]+=delta[now]; delta[now<<1|1]+=delta[now]; sum[now<<1]+=delta[now]; sum[now<<1|1]+=delta[now]; //tr[now<<1]+=delta[now]*d[now<<1]; tr[now<<1|1]+=delta[now]*d[now<<1|1]; delta[now]=0; }}void addsize(int now,int l,int r,int ll,int rr,int v){ if(ll<=l&&r<=rr) { delta[now]+=(LL)v; sum[now]+=(LL)v; //tr[now]+=v*d[now]; return; } pushdown(now); int mid=(l+r)/2; if (ll<=mid) addsize(now<<1,l,mid,ll,rr,v); if (rr>mid) addsize(now<<1|1,mid+1,r,ll,rr,v); update(now);}void changeval(int now,int l,int r,int x,LL v,int pd){ if (l==r) { if (!pd) val[now]+=v; else tr[now]=v; return; } pushdown(now); int mid=(l+r)/2; if (x<=mid) changeval(now<<1,l,mid,x,v,pd); else changeval(now<<1|1,mid+1,r,x,v,pd); update(now);}void solve(int x,int y,int vi){ changeval(1,1,n,pos[y],(LL)size[y]*dis[y],1); changeval(1,1,n,pos[y],(LL)vi*dis[y],0); while (belong[x]!=belong[y]) { addsize(1,1,n,pos[belong[y]],pos[y],vi); changeval(1,1,n,pos[fa[belong[y]]],(LL)vi*dis[fa[belong[y]]],0); y=fa[belong[y]]; } addsize(1,1,n,pos[x],pos[y],vi);}int find(int now,int l,int r){ if (l==r) return l; pushdown(now); int mid=(l+r)/2; if (sum[now<<1|1]*2>=sig) return find(now<<1|1,mid+1,r); else return find(now<<1,l,mid);}LL query(int now,int l,int r,int ll,int rr){ if(ll<=l&&r<=rr) return val[now]; int mid=(l+r)/2; pushdown(now); LL ans=0; if (ll<=mid) ans+=query(now<<1,l,mid,ll,rr); if (rr>mid) ans+=query(now<<1|1,mid+1,r,ll,rr); return ans;}data findpoint(int now,int l,int r,int x){ if (l==r) { data a; a.sum=sum[now]; a.val=val[now]; return a; } int mid=(l+r)/2; pushdown(now); if(x<=mid) return findpoint(now<<1,l,mid,x); else return findpoint(now<<1|1,mid+1,r,x);}LL solve1(int x,int y){ LL ans=0; data a=findpoint(1,1,n,pos[y]); ans-=a.val; while (belong[x]!=belong[y]) { ans+=query(1,1,n,pos[belong[y]],pos[y]); int t=belong[y]; y=fa[belong[y]]; data a=findpoint(1,1,n,pos[y]); data b=findpoint(1,1,n,pos[t]); ans=ans-a.val+dis[y]*(a.sum-b.sum); } ans+=query(1,1,n,pos[x],pos[y]); return ans;}int main(){ freopen("zjoi15_tree.in","r",stdin); freopen("zjoi15_tree.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } dfs(1,0); dfs1(1,1); //for (int i=1;i<=n;i++) cout<<q[i]<<" "; //cout<<endl; memset(size,0,sizeof(size)); build(1,1,n); for (int i=1;i<=m;i++) { int x,k; scanf("%d%d",&x,&k); sig+=k; size[x]+=k; solve(1,x,k); int ap=find(1,1,n); ap=q[ap]; //cout<<ap<<endl; LL ans=0; ans+=(LL)(dis[ap]*sig); ans+=tr[1]; data a=findpoint(1,1,n,pos[ap]); ans-=(LL)2*solve1(1,ap); ans-=(LL)2*dis[ap]*a.sum; PRintf("%lld/n",ans); } }
新聞熱點
疑難解答
