【2019 Multi-University 6 A】Salty Fish 题解

题目大意

  有一棵 $n$ 个结点的树，第 $i$ 个结点有 $a_i$ 的收益。
  还有 $m$ 个摄像头，第 $i$ 个摄像头在 $x_i$ 这个结点上，能监测它子树里所有与 $x_i$ 距离不超过 $k_i$ 的结点（距离按边算），黑掉这个摄像头的代价是 $c_i$。一个结点被任何摄像头监测着它就不能获得收益。
  求最大获益。

  $1 \leq n,m \leq 3 \times 10^5,~1 \leq a_i,c_i \leq 10^9$
  多测，$\sum n \leq 10^6,~\sum m \leq 10^6$
  4s

$$\\$$ $$\\$$ $$\\$$

题解

  首先这是个“最大获利”（学名 最大权闭合图），可以快速建出模型：左边 $m$ 个点表示摄像头，与源点相连，容量为 $c_i$；右边 $n$ 个点表示树上结点，与汇点相连，容量为 $a_i$，然后每个摄像头与它监控的所有结点连边，容量为 $+\infty$。跑最小割即是答案。

  然后这个图太大了，所以要考虑用贪心模拟网络流。

  对于每个点上的摄像头，它的最优方案肯定是先找深度最大的结点来流。因此可以每个点维护一个 set，存这棵子树下每个深度的剩余流量。然后摄像头就贪心地在 set 里找深度最大的去流。

  然后 set 里的内容是以深度为下标的，因此用长链剖分来合并，这样就是 $O(n \log n)$ 的了。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fi first
#define se second
using namespace std;

typedef long long LL;
typedef pair<int,LL> spr;

const int maxn=3e5+5;
const LL inf=1e18;

int n,m,a[maxn];
vector<int> e[maxn];
vector<pair<int,int>> q[maxn];

int maxdeep[maxn],Lson[maxn],deep[maxn];
void dfs_pre(int k,int last)
{
	Lson[k]=0;
	maxdeep[k]=deep[k]=deep[last]+1;
	for(int go:e[k])
	{
		dfs_pre(go,k);
		if (maxdeep[go]>maxdeep[Lson[k]]) Lson[k]=go;
	}
}

LL ans;
set<spr> S[maxn];
int id[maxn];
void merge(int a,int b)
{
	for(spr pr:S[b])
	{
		set<spr>::iterator it=S[a].upper_bound(make_pair(pr.fi,inf));
		if (it==S[a].begin()) continue;
		it--;
		if (it->fi==pr.fi)
		{
			spr now=*it; S[a].erase(now);
			now.se+=pr.se;
			S[a].insert(now);
		} else S[a].insert(pr);
	}
	S[b].clear();
}
void calc(int k)
{
	for(pair<int,int> qi:q[k])
	{
		while (qi.se>0)
		{
			set<spr>::iterator it=S[id[k]].upper_bound(make_pair(qi.fi+deep[k],inf));
			if (it==S[id[k]].begin()) break;
			it--;
			spr now=*it; S[id[k]].erase(now);
			LL nmin=min(now.se,1ll*qi.se);
			ans-=nmin;
			qi.se-=nmin;
			now.se-=nmin;
			if (now.se>0) S[id[k]].insert(now);
		}
	}
}
void dfs(int k)
{
	if (!Lson[k])
	{
		S[k].insert(make_pair(deep[k],a[k]));
		calc(k);
		return;
	}
	dfs(Lson[k]);
	id[k]=id[Lson[k]];
	S[id[k]].insert(make_pair(deep[k],a[k]));
	for(int go:e[k]) if (go!=Lson[k])
	{
		dfs(go);
		merge(id[k],id[go]);
	}
	calc(k);
}

void Clear()
{
	fo(i,1,n)
	{
		e[i].clear(), q[i].clear(), S[i].clear();
		id[i]=i;
	}
	ans=0;
}

int T;
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d %d",&n,&m);
		Clear();
		fo(i,2,n)
		{
			int x;
			scanf("%d",&x);
			e[x].push_back(i);
		}
		fo(i,1,n) scanf("%d",&a[i]), ans+=a[i];
		fo(i,1,m)
		{
			int x,k,c;
			scanf("%d %d %d",&x,&k,&c);
			q[x].push_back(make_pair(k,c));
		}
		
		dfs_pre(1,0);
		
		dfs(1);
		
		printf("%lld\n",ans);
	}
}