思路

考虑到每个节点有限制经过次数，这是关键的约束，经过手动模拟可以发现，到达一个节点意味着消耗一次。剩下的次数代表着可访问的子树数，因为往下走一次在回来需要经过这个节点一次（一定要回来不然回不到根节点了）。

这里面有一个拆分子问题的过程，这提醒我们树形 dp。设 $f[i]$ 表示以 $i$ 为根的子树的最大贡献。$i$ 这个点必选，在它的所有儿子节点中，最多能选 $i$ 的经过次数 -1 个，设这个值为 $k$。则我们在子节点的 $f$ 中选择最多 $\min(k,son)$ 个非负的值加到 $f_i$ 中。

接下来考虑怎么判定是否有不同方案。感性来想，对于每一个节点我们都贪心的尽可能选最大值。这就导致最终方案的限制非常紧，只有在一次决策中出现等价情况才说明有不同方案。因此容易想到几种等价。

• 有 0 可选且正数都选完了还有空余经过次数，这时候选或不选都一样。
• 有多个相等值且一定选且仅选其中一部分。

满足等价就给这个节点打标记，如果它父节点选了它，就可以把标记上传。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+17;
struct node{
	int nxt,to;
}q[N];int head[N],cnt,tp;
void add(int x,int y){
	q[++cnt]=node{head[x],y};
	head[x]=cnt; return;
}
int n,v[N],t[N],f[N],g[N];
int tag[N],tmp[N];
bool cmp(int x,int y){
	return f[x]>f[y];
}
void dfs(int x,int fa){
	f[x]=v[x];
	for(int i=head[x];i;i=q[i].nxt){
		int dd=q[i].to;
		if(dd==fa) continue;
		dfs(dd,x);
		if(tag[dd]) tag[x]=1;
	}tp=0;
	for(int i=head[x];i;i=q[i].nxt){
		if(q[i].to==fa) continue;
		tmp[++tp]=q[i].to;
	}sort(tmp+1,tmp+tp+1,cmp);
	int xx=1,tt;
	for(int i=1;i<=min(t[x]-1,tp);i++){
		if(f[tmp[i]]<0){
			xx=0;break;
		}
		if(f[tmp[i]]==0||tag[tmp[i]]) tag[x]=1;
		f[x]+=f[tmp[i]];tt=i;
	}
	if(xx&&f[tmp[tt]]==f[tmp[tt+1]]&&tt<tp) tag[x]=1;
}
signed main(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> v[i];
	for(int i=1;i<=n;i++) cin >> t[i];
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		add(x,y),add(y,x);
	}t[1]=1e14;dfs(1,0);
	cout << f[1] << '\n';
	if(tag[1]==0) cout << "yes";
	else cout << "no"; 
	return 0;
}

洛谷P6082 [JSOI2015] salesman