分析

处理出子树内剩余删减以及最大的剩余\(a\)和，
如果删了还是超过\(b\)输出无解

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=200011; typedef long long lll; struct rec{lll wt,ws;};
lll ans; int as[N],n,et,flag; struct node{int y,w1,w2,next;}e[N];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
rec dfs(int x){
	rr lll wt=0,ws=0;
	for (rr int i=as[x];i;i=e[i].next){
		if (flag) return (rec){wt,ws};
		rr rec t=dfs(e[i].y);
		if (t.ws-t.wt>e[i].w2){flag=1; return (rec){wt,ws};}
		if (t.ws>e[i].w2) t.wt-=t.ws-e[i].w2,ans+=t.ws-e[i].w2,t.ws=e[i].w2;
		wt+=t.wt+(e[i].w1<e[i].w2?e[i].w1:e[i].w2),ws+=e[i].w1+t.ws;
	}
	return (rec){wt,ws};
}
signed main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n=iut();
	for (rr int i=1;i<n;++i){
		rr int x=iut(),y=iut(),w1=iut(),w2=iut();
		e[++et]=(node){y,w1,w2,as[x]},as[x]=et;
	}
	dfs(1);
	if (flag) printf("-1");
	    else printf("%lld",ans);
	return 0;
}

#贪心，树#C 平衡的树

原文：https://www.cnblogs.com/Spare-No-Effort/p/14062094.html