HDU 6634 Salty Fish (最小割模型 + 长链剖分）

传送门

题意

/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/ 
************************************************************************/

#include
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define LL long long
#define pb push_back
#define fi first
#define se second
#define pr pair
#define mk(a,b) make_pair(a,b)
#define endl '\n'
using namespace std;
const int maxx = 3e5 + 10;
LL n, m, tot, ans, f[maxx], k[maxx], c[maxx], id[maxx], dep[maxx], a[maxx], dis[maxx];
vector e[maxx], ca[maxx];
map M[maxx];
map :: iterator it;
void solve(int x){
	int son = 0;
	for(auto u : e[x]){
		dep[u] = dep[x] + 1;
		solve(u);
		if(dis[u] > dis[son]) son = u;
	}
	dis[x] = dis[son] + 1;
	id[x] = son ? id[son] : ++tot;
	M[id[x]][dep[x]] += a[x];
	for(auto u : e[x]){
		if(u == son) continue;
		for(it = M[id[u]].begin(); it != M[id[u]].end(); ++it) M[id[x]][it->first] += it->second;
		M[id[u]].clear();
	}
	for(auto u : ca[x]){
		it = M[id[x]].upper_bound(dep[x] + k[u]);
		if(it == M[id[x]].begin()) continue;
		--it;
		while(c[u]){
			LL flow = min(it->second, c[u]);
			it->second -= flow;
			c[u] -= flow;
			ans -= flow;
			if(!(it->second)){
				if(it == M[id[x]].begin()){ M[id[x]].erase(it); break; }
				map :: iterator tmp = it;
				--it;
				M[id[x]].erase(tmp);
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out","w", stdout);
#endif
	int T; cin >> T;
	while(T--){
		cin >> n >> m; ans = tot = 0;
		for(int i = 2; i <= n; ++i){ cin >> f[i];  e[f[i]].pb(i); }
		for(int i = 1; i <= n; ++i){ cin >> a[i];  ans += a[i]; }
		// cout << ans << endl;
		for(int i = 1, j; i <= m; ++i){
			cin >> j >> k[i] >> c[i];
			ca[j].push_back(i);
		}
		solve(1); M[id[1]].clear();
		cout << ans << endl;
		for(int i = 0; i <= n; ++i) e[i].clear(), ca[i].clear(), dis[i] = dep[i] = 0;
	}
return 0;
}