Codeforces Round #660 (Div. 2) C. Uncle Bogdan and Country Happiness (DFS)

题意:有\(n\)个人,每个人居住在某个节点,所有人都在节点\(1\)上班,下班后沿着最短路径回家,在回家途中心情可能会变差(心情只会变差不会变好),每个节点都有一个开心值,开心值等于所有经过时的好心情人数减去差心情人数,现在给你每个城市的开心值,问是否满足情况.
题解:这题真的好难想啊,假设第\(i\)个城市经过的好心情的人数是\(good[i]\),差心情是\(bad[i]\),经过的总人数是\(sum[i]\),题目所要求的开心值是\(h[i]\),那么\(good[i]+bad[i]=sum[i]\),\(good[i]-bad[i]=h[i]\),所以得出\(2*good[i]=sum[i]+h[i]\),这要\(good[i]\)合法,就能满足条件,对于\(good[i]\),首先是整数,所以\((h[i]+sum[i])mod\ 2=0\),其次\(0\le good[i]\le sum[i]\),最后因为心情只会变好不会变坏,所以我们统计一下\(i\)下面子节点的\(good\)个数\(s\),满足\(s\le good[i]\)即可.具体实现过程是一个dfs,从\(1\)号节点不断向下搜.

代码:

int t;

int n,m;

int p[N];

int h[N];

vector<int> V[N];

int sum[N],good[N];

bool flag;

void dfs(int u,int fa){

	sum[u]=p[u];

	int s=0;

	for(auto w:V[u]){

		if(w==fa) continue;

		dfs(w,u);

		sum[u]+=sum[w];

		s+=good[w];

	}

	int now=h[u]+sum[u];

	if(now&1){

		flag=false;

		return;

	}

	good[u]=now/2;

	if(good[u]<0 || good[u]>sum[u] || s>good[u]){

		flag=false;

		return;

	}

}

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	scanf("%d",&t);

	while(t--){

		scanf("%d %d",&n,&m);

		for(int i=1;i<=n;++i){

			scanf("%d",&p[i]);

			V[i].clear();

		}

		for(int i=1;i<=n;++i){

			scanf("%d",&h[i]);

		}

		for(int i=1;i<=n-1;++i){

			int u,v;

			scanf("%d %d",&u,&v);

			V[u].pb(v);

			V[v].pb(u);

		}

		flag=true;

		dfs(1,0);

		if(flag) puts("YES");

		else puts("NO");

	}

    return 0;

}

巴特西

Codeforces Round #660 (Div. 2) C. Uncle Bogdan and Country Happiness (DFS)

最新文章

热门文章