Codeforces Round #395 C. Timofey and a tree
2024-08-25 06:24:56
package codeforces;
import java.util.*;
public class CodeForces_764C_Timofey_and_a_tree {
static final int N=(int) (2e5+10);
@SuppressWarnings("unchecked")
static ArrayList<Integer> a[]=new ArrayList[N];
static int book[]=new int[N];
static int c[]=new int[N];
static void dfs(int u,int fa)
{
int v;
for(int i=0; i<a[u].size(); i++)
{
v=(int) a[u].get(i);
if(v!=fa)
{
dfs(v,u);
if(c[v]!=c[u])
{
book[u]++;
book[v]++;
}
}
}
}
static void solve(){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){ int n = sc.nextInt();
int u,v;
for(int i=1; i<n; i++)
{
u=sc.nextInt();
v=sc.nextInt();
if(a[u]==null) a[u]=new ArrayList<Integer>();
if(a[v]==null) a[v]=new ArrayList<Integer>();
a[u].add(v);
a[v].add(u);
}
Arrays.fill(book,0);
for(int i=1; i<=n; i++) c[i]=sc.nextInt();
dfs(1,-1);
int ans2=n,flag=0,maxx=0;
for(int i=1; i<=n; i++)
{
if(book[i]>maxx)
{
maxx=book[i];
ans2=i;
}
}
for(int i=0; i<a[ans2].size(); i++)
{
v=(int)a[ans2].get(i);
book[ans2]-=book[v];
book[v]=0;
}
if(book[ans2]!=0) System.out.println("NO");
else
{
for(int i=1; i<=n; i++)
{
if(book[i]!=0)
{
flag=1;
break;
}
}
if(flag==1) System.out.println("NO");
else
System.out.println("YES\n"+ans2);
}
}
}
public static void main(String args[]){
solve();
}
}
最新文章
- kali4.0 更新源出错
- select的5中子句where,group by, havaing, order by, limit的使用顺序及实例
- mousedown(function(){ return false; })作用
- INFO - InstallShield中的InstallScript工程Setup.exe /s的使用细节
- JS事件大全
- Apache Spark GraphX的体系结构
- nodejs使用express4框架默认app.js配置说明
- Python Socket Programming
- MySQL innotop实时监测工具
- django 模板视图,表单视图,各种视图
- 不可以为null值的自定义类型
- C++默认参数与函数重载 注意事项
- poj 1328 Radar Installation (简单的贪心)
- Java并发编程:线程控制
- 华为oj之字符串最后一个单词的长度
- 20个Chrome DevTools调试技巧
- 生活沉思录 via 哲理小故事(一)
- 文本文件合并(C++实现)
- 更新中国地区ip列表
- 怎样用SQL语句查看查询的性能指标
热门文章
- Android网络相关代码
- mybatis中各种数据的映射类型
- 解决Error for wireless request ";Set Mode"; (8B06) 问题 (转载)
- tar zxvf 解压文件提示错误
- bzoj 1642: [Usaco2007 Nov]Milking Time 挤奶时间【dp】
- Android 性能优化(21)*性能工具之「GPU呈现模式分析」Profiling GPU Rendering Walkthrough:分析View显示是否超标
- jquery中有关cookie的使用简要说明
- LN : leetcode 538 Convert BST to Greater Tree
- C#和Java在语法上的差异(原创,持续更新中)
- 微信小程序组件解读和分析:三、swiper滑块视图