WA9 个求条
查看原帖
WA9 个求条
983519
Laisira楼主2025/1/8 10:45
#include<bits/stdc++.h>
#define int long long 
#define Maxn 100005 
using namespace std;
int w[Maxn];
vector<int> q[Maxn];
int f[Maxn],flag = 0;
void dfs(int x,int fa) {
	if(q[x].size() == 1)return f[x] = w[x],void();
	for(int u:q[x]) {
		if(u == fa)continue;
		dfs(u,x);
		if(flag)return ;
		f[x] += f[u];
	}
	if(f[x] > w[x]*2)return flag = 1/*,cout<<x<<"\n"*/,void();
	f[x] = 2*w[x]-f[x];
}
signed main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	if(n == 2)return cout<<(w[1] == w[2]?"YES":"NO"),0;
	for(int i=1;i<n;i++) {
		int u,v;
		cin>>u>>v;
		q[u].push_back(v);
		q[v].push_back(u);
	} int rt = 1;
	while(q[rt].size() == 1)rt ++;
//	cout<<rt<<"\n";
	dfs(rt,0);
//	for(int i=1;i<=n;i++)cout<<f[i]<<"\n";
	if(!flag&&!f[rt])return cout<<"YES",0;
	cout<<"NO";
	return 0;
 } 
2025/1/8 10:45
加载中...