codeforces 764 C. Timofey and a tree（dfs+思维）
2024-09-01 05:47:59
题目链接：http://codeforces.com/contest/764/problem/C
题意：给出一个树，然后各个节点有对应的颜色，问是否存在以一个点为根节点子树的颜色都一样。
这里的子树颜色都一样表示分出来的子树各自颜色一样。
就是随意找一个树叶节点然后一直遍历，直到找到一个和他颜色不一样的节点，那么要么取不一样的节点
为根或者取最后一个一样的节点为根。然后就dfs一遍。
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int M = 1e5 + 10;
int c[M] , ans , ans2;
vector<int>vc[M];
void dfs1(int sta , int pre , int co) {
if(c[sta] != co) {
ans = sta;
ans2 = pre;
return;
}
int len = vc[sta].size();
for(int i = 0 ; i < len ; i++) {
int v = vc[sta][i];
if(v != pre) {
dfs1(v , sta , co);
}
}
}
bool dfs(int sta , int pre , int co) {
if(c[sta] != co) {
return false;
}
int len = vc[sta].size();
int gg = true;
for(int i = 0 ; i < len ; i++) {
int v = vc[sta][i];
if(v != pre) {
if(!dfs(v , sta , co)) {
gg = false;
}
}
}
if(!gg) {
return false;
}
else {
return true;
}
}
int main() {
int n , u , v;
cin >> n;
for(int i = 0 ; i < n - 1 ; i++) {
cin >> u >> v;
vc[u].push_back(v);
vc[v].push_back(u);
}
for(int i = 1 ; i <= n ; i++) {
cin >> c[i];
}
int sta = 0;
for(int i = 1 ; i <= n ; i++) {
int len = vc[i].size();
if(len == 1) {
sta = i;
break;
}
}
ans = -1 , ans2 = -1;
dfs1(sta , sta , c[sta]);
if(ans == -1) {
cout << "YES" << endl;
cout << sta << endl;
}
else {
int len = vc[ans].size();
bool flag = true;
for(int i = 0 ; i < len ; i++) {
int v = vc[ans][i];
flag = dfs(v , ans , c[v]);
if(!flag)
break;
}
int flag1 = true;
len = vc[ans2].size();
for(int i = 0 ; i < len ; i++) {
int v = vc[ans2][i];
flag1 = dfs(v , ans2 , c[v]);
if(!flag1)
break;
}
if(flag || flag1) {
cout << "YES" << endl;
if(flag) {
cout << ans << endl;
return 0;
}
if(flag1) {
cout << ans2 << endl;
}
}
else {
cout << "NO" << endl;
}
}
return 0;
}
最新文章
- C#自定义工业控件开发
- ORACLE 11g安装
- poj 2481 - Cows(树状数组)
- php的预定义数组
- BGP学习笔记
- 读取、添加、删除、修改配置文件 如（Web.config, App.config)
- sqlite数据库查询批量
- C语言的struct/union字节对齐
- TDBAdvGrid 只读状态下复制功能
- YUV数据格式
- 写入soap消息以及与soap消息通信
- 修改表单元素中placeholder属性样式、清除IE浏览器中input元素的清除图标和眼睛图标
- YII框架CGridView分页实现
- springMVC整理02--常用注解的使用
- PHP no input file specified 三种解决方法
- HDU 1034(传递糖果 模拟)
- python3+requests库框架设计08-发送邮件
- linux 修改内核参数 如何生效？
- yii---解决post请求出现500错误
- Linux怎么开启ssh