Salty Fish[hdu6634]

发表于 分类于

题意

一棵有根树，树上每个节点有 $a_i$ 个苹果。$m$ 个摄像机，每个摄像机可以看到 $x_i$ 的子树中所有与 $x_i$ 距离不超过 $k_i$ 的点中的苹果，可以花钱 $c_i$ 使该摄像机失效。求最终没有被看到的苹果数 - 花费的钱的最大值。

$n,m\leq 3\times 10^5$ , $\sum n,\sum m\leq 10^6$

题解

建模

假设全部先选了所有的苹果，然后考虑放弃那些比较合适。

考虑最小割建图，$S$ 连每个摄像机，边权为 $c_i$；每个摄像机连对应的树上的点，边权为 $\infty$；每个树上的点连 $T$，权值为 $a_i$。

那么减去最小割就是答案了。

显然不能直接跑网络流，尽管线段树优化建图也不行。

那就只能模拟网络流了。

模拟网络流

贪心处理。

从叶节点往上推，把摄像机挂在树上。

每遇到一个摄像机都用当前深度最大的点去跟它抵消。

那么对于每个节点 $i$ 只需要记 $f_{i,j}$ 表示深度为 $j$ 的所有点还剩多少流量。

可以用 $\mbox{map}$ 维护。

合并的时候用启发式合并。这个只跟深度有关，因此长链剖分即可。

每个摄像机只会删除，不会令 $\mbox{map}$ 中的元素增加。

时间复杂度 $O((n+m)\log n)$

程序

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
struct node{
	int d,c;
};
map<int,ll> f[N];
map<int,ll>::iterator it;
vector<node> q[N];
int a[N];
ll ans;
int n,m,cnt;
int ver[N],ne[N],head[N],tot;
inline void add(int x,int y)
{
	ver[++tot]=y; ne[tot]=head[x]; head[x]=tot;
}
int mx[N],son[N],dep[N],id[N];
void dfs(int u,int pre)
{
	dep[u]=dep[pre]+1;
	for(int i=head[u],v;i;i=ne[i])
	{
		v=ver[i];
		dfs(v,u);
		if(mx[son[u]]<mx[v]) son[u]=v;
		mx[u]=max(mx[u],mx[v]);
	}
	mx[u]++;
}
void dfs(int u)
{
	if(son[u]) dfs(son[u]),id[u]=id[son[u]];
	else id[u]=++cnt;
	f[id[u]][dep[u]]+=a[u];
	for(int i=head[u],v;i;i=ne[i])
	if((v=ver[i])!=son[u])
	{
		dfs(v);
		for(it=f[id[v]].begin();it!=f[id[v]].end();it++)
			f[id[u]][(*it).fi]+=(*it).se;
	}
	int d,c;
	fo(i,0,q[u].size()-1)
	{
		d=q[u][i].d,c=q[u][i].c;
		it=f[id[u]].upper_bound(dep[u]+d);
		if(it==f[id[u]].begin()) continue;
		for(it--;c;)
		{
			ll w=min((ll)c,(*it).se);
			(*it).se-=w; ans-=w; c-=w;
			if(!(*it).se)
			{
				if(it==f[id[u]].begin()) {f[id[u]].erase(it); break;}
				int t=(*it).fi;
				it--;
				f[id[u]].erase(t);
			}
		}
	}
}

inline void init()
{
	fo(i,1,n) head[i]=mx[i]=dep[i]=son[i]=id[i]=0,q[i].clear();
	fo(i,1,cnt) f[i].clear();
	ans=cnt=tot=0;
}

int main()
{
	for(int _=read(),x,k,c;_--;)
	{
		n=read(); m=read();
		init();
		fo(i,2,n) add(read(),i);
		fo(i,1,n) a[i]=read(),ans+=a[i];
		fo(i,1,m) x=read(),k=read(),c=read(),q[x].pb((node){k,c});
		dfs(1,0);
		dfs(1);
		printf("%lld\n",ans);
	}
	return 0;
}