正文

cf763atimofeyandatree（思维题）

leonard-  leonard-  2022-10-09  189

关键词：

题目链接：http://codeforces.com/problemset/problem/763/A

题目：

Each New Year Timofey and his friends cut down a tree of n vertices and bring it home. After that they paint all the n its vertices, so that the i-th vertex gets color ci.

Now it‘s time for Timofey birthday, and his mother asked him to remove the tree. Timofey removes the tree in the following way: he takes some vertex in hands, while all the other vertices move down so that the tree becomes rooted at the chosen vertex. After that Timofey brings the tree to a trash can.

Timofey doesn‘t like it when many colors are mixing together. A subtree annoys him if there are vertices of different color in it. Timofey wants to find a vertex which he should take in hands so that there are no subtrees that annoy him. He doesn‘t consider the whole tree as a subtree since he can‘t see the color of the root vertex.

A subtree of some vertex is a subgraph containing that vertex and all its descendants.

Your task is to determine if there is a vertex, taking which in hands Timofey wouldn‘t be annoyed.

Input

The first line contains single integer n (2 ≤ n ≤ 105) — the number of vertices in the tree.

Each of the next n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), denoting there is an edge between vertices u and v. It is guaranteed that the given graph is a tree.

The next line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 105), denoting the colors of the vertices.

Output

Print "NO" in a single line, if Timofey can‘t take the tree in such a way that it doesn‘t annoy him.

Otherwise print "YES" in the first line. In the second line print the index of the vertex which Timofey should take in hands. If there are multiple answers, print any of them.

Examples

input

output

YES
2

input

output

YES
2

input

output

NO

题意：给定一棵每个顶点都标记颜色的树，问能否从一个顶点出发，使得它的子树都是一样颜色（不包括这个顶点本身的颜色）。

题解：因条件要求，我们可以知道不同的颜色的顶点中其中一个必须是答案顶点，我们统计一下不同颜色顶点个数（设为m），和不同颜色顶点中顶点出现次数。最后如果有一个顶点出现次数等于m，那么这个顶点就是答案顶点。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define PI acos(-1.0)
 5 #define INF 0x3f3f3f3f
 6 #define FAST_IO ios::sync_with_stdio(false)
 7 #define CLR(arr,val) memset(arr,val,sizeof(arr))
 8 
 9 const int N=1e5+1234;
10 typedef long long LL;
11 struct node{
12     int u,v;
13 }T[N];
14 int col[N],cnt[N];
15 
16 int main(){
17     int n,m=0;
18     cin>>n;
19     for(int i=1;i<n;i++) cin>>T[i].u>>T[i].v;
20     for(int i=1;i<=n;i++) cin>>col[i];
21     for(int i=1;i<n;i++){
22         if(col[T[i].u]!=col[T[i].v]){
23             cnt[T[i].u]++;cnt[T[i].v]++;
24             m++;
25         }
26     }
27     for(int i=1;i<=n;i++){
28         if(cnt[i]==m){
29             cout<<"YES"<<endl;
30             cout<<i<<endl;
31             return 0;
32         }
33     }
34     cout<<"NO"<<endl;
35     return 0;
36 }

思维思维题——cf1350d(代码片段)

很有意思的题目，感觉看智商。。/*结论：显然只要成功操作一次，就可以把整个数组变成k如何找到这一次操作？把<k,=k,>k的数变成012显然只要存在11,12,101,102,这种类型，就必定可以操作成功一次结论：只要存在1，且存在|i-j... 查看详情

树上思维题——cf1060e

只要算每条路径的贡献即可显然长度为偶数的贡献是len/2长度为奇数的贡献是（len+1）/2所以结果就是（sum+tot）/2sum:路径总长tot:奇数路径数量怎么求奇数路径数量：只有深度为奇数+深度为偶数的点才能组成奇数路径，求一下... 查看详情

cf763b.timofeyandrectangles

%%题解，脑洞好大啊。四色定理什么鬼的。。所以一定是yes。因为矩形边长都是奇数，所以可以按左下角分类，一共4类，分别1,2,3,4就可以了。（需要4种颜色的情况大概就是4个矩形围起来一个矩形）1#include<bits/stdc++.h>2#defineL... 查看详情

cf745d交互题思维二进制分解

现有一矩阵你可以做出不超过20个询问每个询问要求输入列号，可以询问矩阵上每行上你给的列之中的最小值让你最后输出该矩阵每行的不包括对角线位置上的最小值考虑询问如何分组，考虑二分，以二进制位来分组那么最多不... 查看详情

cf1025c思维题(代码片段)

/*bwwwbwwbwwwbwwwbwb不管从哪里断开翻转。翻转后的串再整体翻转一定是2s的子串*/#include<bits/stdc++.h>usingnamespacestd;intlen;chars[1000000];intmain()cin>>s+1;intlen=strlen(s+1);if(len==1)puts("1");return0;for(inti=len+1;i<=len*2;i++)s[i]=s[i-len];intans=0,l=0;... 查看详情

思维思维题——cf1350d(代码片段)

cf1216e2numericalsequence(hardversion)二分查找思维题(代码片段)

题目描述Theonlydifferencebetweentheeasyandthehardversionsisthemaximumvalueofk.Youaregivenaninfinitesequenceofform"112123123412345……"whichconsistofblocksofallconsecutivepositiveintegerswrittenoneafteranother.Thefirstblockconsistsofallnumbersfrom1to1,thesecondone—from1to2,thethirdo... 查看详情

思维题(取模)|cf#615div3d.mexmaximizing

考虑题目中，当前数组中每个数都可进行+x、-x操作。所以要想到与“mod剩余系”有关。构造数中各个数对x取mod的值的出现的次数，当MEX%x的出现次数>=当前MEX/X+1时说明数组中存在多余的一个数可以拿出来一直进行+x操作使它等... 查看详情

毒瘤思维题汇总

...试题和比赛题中没想出来的题（所以可能不仅仅是毒瘤的思维题，还有可能有简单的思维题以及窜进来的数学数据结构之类的题）。可能会有一少部分的平时的练习题。CF351EJeffandPermutation给出数组(a),你可以改变每个数的正负，... 查看详情

cf1348dphoenixandscience（思维）(代码片段)

本题没有无解情况，因为这题本质上可以通过二进制叠加，并且我们知道所有数都能被这样表示对于有解情况，显然每次跳跃的越多越好，但是这是有限制的，一个分裂的总数不能超过当前的个数第二个是当前分裂完后，要保证... 查看详情

[cf1009b]minimumternarystring(思维)(代码片段)

...作（可以是0次）能得到的最小字典序的串是什么。题解思维题关键是把题意理解为：固定0、2的相对位置，往里随意放1，能得到的最小字典序。显然，目标是把所有1放到0后1前好，故放到第一个2222前，若没有2则放到字符串最查看详情

bzoj2296:pojchallenge随机种子(思维题/水题)

　　有点类似CF某场div2T1...　　前面接上1234567890000000，后面加上x+(1234567890000000%x)就可以保证是x的倍数了#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm>#def 查看详情

2022/7/14cf训练(思维+构造+差分)(代码片段)

C.HelpingtheNature一道构造题。难度：1700题意：经过题目给定三种操作，1~i都减去1、i~n都减去1、1~n都加上1，使得数组中所有值都为0，问最少需要多少次操作。思路：乍一看觉得不难，但有几个点需要相... 查看详情

题解-cf1375einversionswapsort(代码片段)

...(1lea_ile10^9)。很明显我的脑子被瘟化课搞残了，这整场的思维题，做出三道就脑子爆出弹簧了。于是只做出(3)题，扣了(95)分。查看详情

cf1028dorderbook思维(代码片段)

Orderbooktimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputLet‘sconsiderasimplifiedversionoforderbookofsomestock.Theorderbookisalistoforders(offers)frompeople 查看详情

cf1028crectangles思维(代码片段)

Rectanglestimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputYouaregiven nn rectanglesonaplanewithcoordinatesoftheirbottomleftandupperrightpoin 查看详情

cf729d模拟，思维

...有射中，求最少再开几枪可射中一只船。题解：转变一下思维，求开了k枪后可放入多少只船。要求再开几枪可射中一只船，只要-a+1即可。#include<bits/stdc++.h>usingnamespacestd;#pragmacomment(linker,"/STACK:102400000,1024 查看详情

力扣算法jslc[435.无重叠区间]lc[763.划分字母区间]

菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后一起坚持每天的算法之旅。希望我们共同进步，一起加油。菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后... 查看详情