http://codeforces.com/contest/764/problem/C

题意:在n个顶点中随便删除一个,然后分成若干个连通子图,要求这若干个连通子图的颜色都只有一种。

记得边是双向的,wa15的可能是不知道边是双向的吧。

一个观察:如果某条边连接的两个顶点的颜色不同,那么可以看看删除这两个顶点,成立就成立,不成立就不成立。

因为必定要把这两个顶点分开。

然后就是暴力dfs了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset> const int maxn = 2e6 + ;
struct node {
int u, v, tonext;
}e[maxn];
int num;
int first[maxn];
void add(int u, int v) {
num++;
e[num].u = u;
e[num].v = v;
e[num].tonext = first[u];
first[u] = num;
}
int c[maxn], in[maxn];
int u[maxn], v[maxn];
set<int>ss;
int vis[maxn];
int DFN;
int dfs(int cur, int no) {
ss.insert(c[cur]);
if (ss.size() >= ) return false;
bool flag = true;
for (int i = first[cur]; i; i = e[i].tonext) {
if (e[i].v == no) continue;
if (vis[e[i].v] == DFN) continue;
vis[e[i].v] = DFN;
flag = flag && dfs(e[i].v, no);
}
return flag;
}
bool del(int cur) {
for (int i = first[cur]; i; i = e[i].tonext) {
ss.clear();
DFN++;
vis[cur] = DFN;
vis[e[i].v] = DFN;
if (dfs(e[i].v, inf) == false) return false;
}
return true;
}
void work() {
int n;
cin >> n;
for (int i = ; i <= n - ; ++i) {
cin >> u[i] >> v[i];
}
for (int i = ; i <= n; ++i) {
cin >> c[i];
}
int which = inf;
for (int i = ; i <= n - ; ++i) {
if (c[u[i]] != c[v[i]] && which == inf) which = i;
add(u[i], v[i]);
add(v[i], u[i]);
}
if (which == inf) {
cout << "YES" << endl;
cout << << endl;
return;
}
// cout << which << " " << root << endl;
if (del(u[which])) {
cout << "YES" << endl;
cout << u[which] << endl;
return;
}
if (del(v[which])) {
cout << "YES" << endl;
cout << v[which] << endl;
return;
}
cout << "NO" << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}

最新文章

  1. 我的android学习经历34
  2. bootstrap-6
  3. [RMQ] [线段树] POJ 3368 Frequent Values
  4. Altium Designer学习: 原理图和PCB元件对应查找
  5. 对List对象按照某个成员变量进行排序
  6. Android便携式热点的开启状态检测和SSID的获取
  7. windows phone 8.1开发:触控和指针事件1
  8. Leetcode_141_Linked List Cycle
  9. PyCharm专业版的安装与破解
  10. geoserver 安装部署发布
  11. IdentityServer4中Code/Token/IdToken对应可访问的资源(api/identity)
  12. LinuxMint下的Orionode源码安装
  13. The Dominator of Strings HDU - 6208(ac自动机板题)
  14. 面向对象(基础oop)之继承总结
  15. 【SSH网上商城项目实战23】完成在线支付功能
  16. pytorch rnn
  17. java 获取今天,昨天,上个月的日期
  18. MySQL优化--创建索引,以及怎样索引才会生效 (03)
  19. 阿里云两台服务器之间拷贝文件命令scp
  20. 搭建 github.io 博客站点

热门文章

  1. unique函数(STL)
  2. 把A表中的a字段和b字段数据 复制到B表中的aa字段和bb字段
  3. [LeetCode][Java] Roman to Integer
  4. HDU 4277 USACO ORZ(暴力+双向枚举)
  5. Xcode中使用git
  6. Library Project里面使用Case语句判断R.id值报错。case expressions must be constant expressions
  7. 2016/5/6 thinkphp ①框架 ② 框架项目部署 ③MVC模式 ④控制器访问及路由解析 ⑤开发和生产模式 ⑥控制器和对应方法创建 ⑦视图模板文件创建 ⑧url地址大小写设置 ⑨空操作空控制器 ⑩项目分组
  8. Infrastructure for container projects.
  9. php判断手机号码
  10. XMU 1607 nc与点对距离 【线段树】