NKOJ 3254 （ZJOI 2015）幻想乡战略游戏（点分治）

发表于 |
字数统计: 1,678字 | 阅读时长 ≈ 8min

P3254【ZJOI2015 Day1】幻想乡战略游戏

问题描述

傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。
在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。
整个地图是一个树结构，一共有n块空地，这些空地被n-1条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。
如果补给站在点u上，并且空地v上有dv个单位的军队，那么幽香每天就要花费dv×dist(u,v)的金钱来补给这些军队。由于幽香需要补给所有的军队，因此幽香总共就要花费这里写图片描述的代价。
其中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）。数据保证任何时刻每个点上的军队数量都是非负的。

输出格式

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

样例输入

10 5
1 2 1
2 3 1
2 4 1
1 5 1
2 6 1
2 7 1
5 8 1
7 9 1
1 10 1
3 1
2 1
8 1
3 1
4 1

样例输出

0
1
4
5
6

提示

对于所有数据，1<=c<=1000, 0<=|e|<=1000, n<=105, Q<=105。
非常神奇的是，对于所有数据，这棵树所有节点的度数都不超过20，并且n,Q>=1。

此题的关键是动态查找带权重心，而关于带权重心，对于一个点$u$，如果它不是带权重心，那么带权重心只可能在它权值最大的儿子里面，如果不存在比他更有的儿子，那么他就是带权重心。
因此只需要找到带权重心后统计答案即可，每次从根节点开始找，直到找到带权重心为止，考虑到这样找可能深度比较深，用点分治维护，每次找到一个更优的儿子的时候，跳到这个儿子所在子树的点分治重心即可。
另外需要支持修改。复杂度$O(nlog^2n)$

另外，由于这个题数据的问题，导致每次暴力从上次的重心开始，在原树上直接转移重心比点分治跑得更快。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 400005
#define ll long long
using namespace std;
ll n,q,E[N],Top,Tot;
ll Min,si[N],rt;
bool mark[N];
ll TOT,LA[N],NE[N],EN[N],LE[N];
ll V[N],S[N],D[N],dep[N],fa[N],to[N][25],TO[N][25],ace[N][25],dis[N][25],S1[N][25],S2[N][25];
void ADD(ll x,ll y,ll z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void Grt(ll x,ll s,ll f)
{
	ll i,y,Max=0;si[x]=1;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(mark[y]||y==f)continue;
		Grt(y,s,x);si[x]+=si[y];
		if(si[y]>Max)Max=si[y];
	}
	if(s-si[x]>Max)Max=s-si[x];
	if(Max<Min)Min=Max,rt=x;
}
void Gdis(ll x,ll f,ll d,ll p,ll ty)
{
	ace[x][dep[p]]=ty;
	dis[x][dep[p]]=d;
	S1[p][ty]+=E[x];
	S2[p][ty]+=E[x]*d;
	for(ll i=LA[x];i;i=NE[i])
	if(EN[i]!=f&&!mark[EN[i]])Gdis(EN[i],x,d+LE[i],p,ty);
}
void DC(ll x)
{
	int i,y;mark[x]=1;V[x]=E[x];
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(mark[y])continue;
		D[x]++;to[x][D[x]]=y;
		Min=1e9;Grt(y,si[y],0);
		Gdis(y,0,LE[i],x,D[x]);
		TO[x][D[x]]=rt;
		V[x]+=S1[x][D[x]];
		S[x]+=S2[x][D[x]];
	}
	for(i=1;i<=D[x];i++)
	{
		y=TO[x][i];
		dep[y]=dep[x]+1;
		fa[y]=x;
		DC(y);
	}
}
void CHA(ll x,ll d)
{
	ll i,j,k,y,p;
	E[x]+=d;V[x]+=d;
	p=fa[x];
	while(p)
	{
		k=ace[x][dep[p]];
		V[p]+=d;
		S[p]+=d*dis[x][dep[p]];
		S1[p][k]+=d;
		S2[p][k]+=d*dis[x][dep[p]];
		p=fa[p];
	}
}
ll Gans(ll x)
{
	ll i,y,p=fa[x],s=S[x];
	while(p)
	{
		s+=E[p]*dis[x][dep[p]];
		for(i=1;i<=D[p];i++)
		{
			if(i==ace[x][dep[p]])continue;
			s+=S2[p][i]+S1[p][i]*dis[x][dep[p]];
		}
		p=fa[p];
	}
	return s;
}
ll Find(ll x)
{
	ll i,y,p=x,las,Las=Gans(p),t;
	while(p)
	{
		las=p;
		for(i=1;i<=D[p];i++)
		{
			y=to[p][i];t=Gans(y);
			if(t<Las){p=TO[p][i];Las=Gans(p);break;}
		}
		if(las==p)break;
	}
	return Las;
}
int main_main()
{
	ll i,j,k,x,y,z;
	scanf("%lld%lld",&n,&q);
	for(i=1;i<n;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		ADD(x,y,z);ADD(y,x,z);
	}
	Min=1e9;Grt(1,n,0);Top=rt;DC(rt);
	while(q--)
	{
		scanf("%lld%lld",&x,&k);
		CHA(x,k);Tot+=k;
		y=Find(Top);
		printf("%lld\n",y);
	}
}
const int main_stack=16;
char my_stack[128<<20];
int main() {
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");
  main_main();
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");
  return 0;
}