P4629 [SHOI2015]聚变反应炉

考虑树形(dp)

令(f(n))表示激发了(n)的子树内的所有点，且在(fa(n))之前激发(n)的最小花费

令(g(n))表示激发了(n)的子树内的所有点，且在(fa(n))之后激发(n)的最小花费

那么我们根据这个(dp)即可

具体的，在对每一个点算贡献的时候，另外开一个数组(h(n))表示从这个点儿子处传上来(n)的能量的最小贡献，转移时考虑这个儿子的状态以及父亲的状态即可

#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 100000
using namespace std;

int n, d[maxn + 5], c[maxn + 5], hd[maxn + 5], len = 0;
LL f[maxn + 5], g[maxn + 5];
struct Edge{int v, net;} e[2 * maxn + 5];
void add(int u, int v){e[len] = (Edge){v, hd[u]}; hd[u] = len++;}

template <class T>
void read(T &x){
	char ch;
	bool ok;
	for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
	for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	if(ok) x = -x;
}

void chkmn(LL &x, LL y){if(x > y) x = y;}

namespace c1{
	LL h[5 * maxn + 5];
	void dfs(int u, int pre){
		LL sum = 0;
		Tra(u, i){
			int v = e[i].v;
			if(v == pre) continue;
			sum += c[v];
			dfs(v, u);
		}
		memset(h, inf, sizeof h); h[0] = 0;
		Tra(u, i){
			int v = e[i].v;
			if(v == pre) continue;
			Rof(j, sum, 0){
				h[j] += g[v];
				if(j >= c[v]) chkmn(h[j], h[j - c[v]] + f[v]);	
			}
		}
		For(i, 0, sum){
			chkmn(f[u], h[i] + max(0, d[u] - i));
			chkmn(g[u], h[i] + max(0, d[u] - i - c[pre]));
		}
	}
	void work(){
		memset(f, inf, sizeof f);
		memset(g, inf, sizeof g);
		dfs(1, 0);
		printf("%lld
", f[1]);
	}
}

namespace c2{
	void dfs(int u, int pre){
		LL val = 0;
		set<pair<LL, int> > se;
		Tra(u, i){
			int v = e[i].v;
			if(v == pre) continue;
			dfs(v, u);
			val += g[v];
			if(c[v]) se.insert(mp(f[v] - g[v], v));
		}
		chkmn(f[u], val + d[u]);
		chkmn(g[u], val + max(0, d[u] - c[pre]));
		For(i, 1, n){
			if(!se.size()) break;
			pair<int, int> tem = *se.begin(); se.erase(tem);
			val += tem.fir;
			chkmn(f[u], val + max(0, d[u] - i));
			chkmn(g[u], val + max(0, d[u] - i - c[pre]));
		}
	}
	void work(){
		memset(f, inf, sizeof f);
		memset(g, inf, sizeof g);
		dfs(1, 0);
		printf("%lld
", f[1]);
	}
}

int main(){
	//freopen("fusion.in", "r", stdin);
	//freopen("fusion.out", "w", stdout);
	memset(hd, -1, sizeof hd);
	read(n);
	For(i, 1, n) read(d[i]);
	For(i, 1, n) read(c[i]);
	For(i, 1, n - 1){
		int u, v; read(u); read(v);
		add(u, v); add(v, u);
	}
	if(n <= 2000) c1::work();
	else c2::work();
	return 0;
}