欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

CodeForces - 1118F1 Tree Cutting (Easy Version) (树形dp/dfs+思维)

程序员文章站 2022-04-01 12:41:36
Tree Cutting (Easy Version) 题目大意:有一颗树,每个节点有三种颜色,红蓝或者无色,问你怎样分割可以把树分成两半并且红色还有蓝色分别位于两边。解题思路:首先我们先记录一下红蓝节点分别有多少个,然后跑一遍dfs记录每个节点的子树上的红蓝节点的个数,最后遍历一下,如果红色节点=x蓝色 =0,或者红色=0蓝色=y,ans++即可Code:#include #include #include...

Tree Cutting (Easy Version)

题目大意:
有一颗树,每个节点有三种颜色,红蓝或者无色,问你怎样分割可以把树分成两半并且红色还有蓝色分别位于两边。

解题思路:
首先我们先记录一下红蓝节点分别总共有多少个,然后跑一遍dfs记录每个节点的子树上的红蓝节点的个数,最后遍历一下,如果红色节点=x蓝色 =0,或者红色=0蓝色=y,ans++即可
Code:

#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define inf 9654234
#define ll long long
using namespace std;
const int maxn=300007;

vector<int> ve[maxn];
int a[maxn],red[maxn],bule[maxn],x=0,y=0,ans=0;

void dfs(int u,int fa){
	if(a[u]==1) red[u]=1;
	if(a[u]==2) bule[u]=1;
	for(auto v:ve[u]){
		if(v==fa) continue;
		dfs(v,u);
		red[u]+=red[v];
		bule[u]+=bule[v];
	}
}

void solve(int u,int fa){
	for(auto v:ve[u]){
		if(v==fa) continue;
		solve(v,u);
		if(red[v]==x&&bule[v]==0||red[v]==0&&bule[v]==y) ans++;
		
	}
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		if(a[i]==1) x++;
		if(a[i]==2) y++;
	}
	
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	
	dfs(1,0);
	solve(1,0);
//	cout<<x<<' '<<y<<endl;
	cout<<ans<<"\n";
	return 0;
}

本文地址:https://blog.csdn.net/weixin_43872264/article/details/107892126

相关标签: 树形DP dfs