【BZOJ3924】幻想乡战略游戏（动态点分治）

题面

权限题。。。（穷死我了）

洛谷

题解

考虑不修改

发现一个贪心的做法

假设当前放在当前位置

如果它有一个子树的兵的总数大于总数的一半

那么，放到那个子树的根节点上一定最优

那么，现在是动态修改

考虑动态点分治

在每个点上维护子树的兵的总数

子树到上一层父亲节点

向上走产生的贡献的总和

以及接收到子节点的贡献的总和

那么，就可以计算当前点产生的贡献

于是，从分治树根开始向下贪心即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 120000

#define ll long long

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

struct Line{int v,next,w,rt;}e[MAX<<1],E[MAX<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w,0};h[u]=cnt++;}

int H[MAX],Cnt=1;

inline void ADD(int u,int v,int rt){E[Cnt]=(Line){v,H[u],0,rt};H[u]=Cnt++;}

/************************************************************************/

int dfn[MAX],top[MAX],dep[MAX],ssize[MAX],hson[MAX],fa[MAX];

int dis[MAX];

void dfs1(int u,int ff)

{

	fa[u]=ff;ssize[u]=1;dep[u]=dep[ff]+1;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;

		if(v==ff)continue;

		dis[v]=dis[u]+e[i].w;

		dfs1(v,u);

		ssize[u]+=ssize[v];

		if(ssize[hson[u]]<ssize[v])hson[u]=v;

	}

}

void dfs2(int u,int tp)

{

	top[u]=tp;

	if(hson[u])dfs2(hson[u],tp);

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;

		if(v==fa[u]||v==hson[u])continue;

		dfs2(v,v);

	}

}

int LCA(int u,int v)

{

	while(top[u]!=top[v])

	{

		if(dep[top[u]]<dep[top[v]])swap(u,v);

		u=fa[top[u]];

	}

	return dep[u]<dep[v]?u:v;

}

int Dis(int u,int v)

{

	return dis[u]+dis[v]-dis[LCA(u,v)]*2;

}

/************************************************************************/

int sum[MAX],size[MAX],Fa[MAX];

int n,Q;

ll td[MAX],tf[MAX];

int Size,root,minr;

bool vis[MAX];

void Getroot(int u,int ff)

{

	size[u]=1;

	int ret=0;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;

		if(v==ff||vis[v])continue;

		Getroot(v,u);

		size[u]+=size[v];

		ret=max(ret,size[v]);

	}

	ret=max(ret,Size-size[u]);

	if(ret<minr)minr=ret,root=u;

}

void DFS(int u,int ff)

{

	vis[u]=true;Fa[u]=ff;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;

		if(vis[v])continue;

		minr=n;Size=size[v];

		Getroot(v,u);

		ADD(u,v,root);

		DFS(root,u);

	}

}

void Modify(int u,int w)

{

	sum[u]+=w;

	for(int i=u;Fa[i];i=Fa[i])

	{

		int dist=Dis(u,Fa[i]);

		sum[Fa[i]]+=w;

		td[Fa[i]]+=1ll*w*dist;

		tf[i]+=1ll*w*dist;

	}

}

ll Count(int u)

{

	ll ret=td[u];

	for(int i=u;Fa[i];i=Fa[i])

	{

		int dist=Dis(u,Fa[i]);

		ret+=1ll*(sum[Fa[i]]-sum[i])*dist;

		ret+=td[Fa[i]]-tf[i];

	}

	return ret;

}

ll Query(int u)

{

	ll tmp=Count(u);

	for(int i=H[u];i;i=E[i].next)

		if(Count(E[i].v)<tmp)return Query(E[i].rt);

	return tmp;

}

int main()

{

	n=read();Q=read();

	for(int i=1,a,b,c;i<n;++i)

	{

		a=read(),b=read(),c=read();

		Add(a,b,c),Add(b,a,c);

	}

	dfs1(1,0);dfs2(1,1);

	minr=Size=n;Getroot(1,0);

	int RT=root;

	DFS(root,0);

	while(Q--)

	{

		int u=read(),v=read();

		Modify(u,v);

		printf("%lld\n",Query(RT));

	}

	return 0;

}