bzoj 3924: [Zjoi2015]幻想乡战略游戏 （树链剖分）

Description

 傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。 在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。 整个地图是一个树结构，一共有n块空地，这些空地被n-1条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。 如果补给站在点u上，并且空地v上有dv个单位的军队，那么幽香每天就要花费dv×dist(u,v)的金钱来补给这些军队。由于幽香需要补给所有的军队，因此幽香总共就要花费为Sigma(Dv*dist(u，v),其中1<=V<=N)的代价。其中dist(u,v)表示u个v在树上的距离（唯一路径的权和）。 因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动他的补给站从而省一些钱。但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？ 你可以假定一开始所有空地上都没有军队。 

Input

第一行两个数n和Q分别表示树的点数和幽香操作的个数，其中点从1到n标号。 接下来n-1行，每行三个正整数a,b,c，表示a和b之间有一条边权为c的边。 接下来Q行，每行两个数u,e，表示幽香在点u上放了e单位个军队（如果e<0，就相当于是幽香在u上减少了|e|单位个军队，说白了就是du←du+e）。数据保证任何时刻每个点上的军队数量都是非负的。 

Output

 对于幽香的每个操作，输出操作完成以后，每天的最小花费，也即如果幽香选择最优的补给点进行补给时的花费。 

Sample Input

Sample Output

HINT

Source

题解：树链剖分

这道题应该是动态点分治，但是也可以用树链剖分来做，只不过比较麻烦。。。。

先考虑如何找到最优的位置。

应该是邮局选址问题，找到第一个大于等于总军队数一半的位置就是最合适的位置。从这个位置往任意方向移动，答案都不会变小。对应到树上就是，找到深度最深的大于等于总军队数一半的节点。这个可以链剖后用线段树维护。每次一个点的军队数量修改，该点到根路径上所有点的权值都进行修改。在查询的时候，因为链剖得到的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);	} }