正文

codeforces763a.timofeyandatree（dfs）(代码片段)

小坏蛋_千千  小坏蛋_千千  2022-10-22  807

关键词：

Description

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 ≤ 10^5) — 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 ≤ 10^5), 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

Examples output

YES
2

题意

给定一棵树，树中的每个节点都有其固定的颜色，问能否找到一个节点，使得与该节点相连的每个子树只包含一种颜色。

思路

仔细想想便可以知道，我们只需要找出与当前节点不同颜色的邻接点数目最大的那个点，然后对其相连的子树一一判断即可。

若其他子树每个只包含一种颜色则为 YES ，否则为 NO 。

AC 代码

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);\\
    cin.tie(0);\\
    cout.tie(0);
using namespace std;
const int maxn = 1e5+10;
typedef __int64 LL;

struct node

    int to;
    int next;
 edge[maxn<<1];
int head[maxn],tot;
int color[maxn];
int n,now;
bool flag = true;

void init()

    memset(head,-1,sizeof(head));
    tot = 0;


void addedge(int u,int v)

    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;


void dfs(int x,int fa)

    if(color[x]!=now)
    
        flag = false;
        return;
    
    for(int i=head[x]; i!=-1; i=edge[i].next)
    
        int to = edge[i].to;
        if(to==fa)
            continue;
        dfs(to,x);
        if(!flag)
            return;
    


int main()

    IO;
    init();
    cin>>n;
    for(int i=1; i<n; i++)
    
        int u,v;
        cin>>u>>v;
        addedge(u,v);
        addedge(v,u);
    
    for(int i=1; i<=n; i++)
    
        cin>>color[i];
    
    int ansv = -1,maxv = -1;
    for(int i=1; i<=n; i++)
    
        int tmp = 0;
        for(int j=head[i]; j!=-1; j=edge[j].next)
        
            if(color[edge[j].to]!=color[i])
                tmp++;
        
        if(tmp>maxv)
        
            maxv = tmp;
            ansv = i;
        
    
    for(int i=head[ansv]; i!=-1; i=edge[i].next)
    
        now = color[edge[i].to];
        dfs(edge[i].to,ansv);
        if(!flag)
        
            cout<<"NO"<<endl;
            break;
        
    
    if(flag)
        cout<<"YES"<<endl<<ansv<<endl;
    return 0;

codeforces763a.timofeyandatree

A.Timofeyandatree题意：给一棵树，要求判断是否存在一个点，删除这个点后，所有连通块内颜色一样。$N,Cle10^5$想法：这个叫换根吧。先求出一个点合法即其儿子的子树内颜色一样，非该点子树的点颜色都一样。可以用DFS序解决。&n... 查看详情

cf763atimofeyandatree（思维题）

题目链接：http://codeforces.com/problemset/problem/763/A题目：EachNewYearTimofeyandhisfriendscutdownatreeof n verticesandbringithome.Afterthattheypaintallthe n itsvertices,sothatthe i 查看详情

codeforcesround#763(div.2)editorialc解题报告(代码片段)

链接：https://codeforces.com/contest/1623/problem/C题解：二分答案即可。比较困扰我的是两个问题：1.怎么求出ddd。2.如何判断这个midmidmid的值是否合法。会不会出现，满足check,但是实际上不存在midmidmid的情况。第一个:intd&... 查看详情

763.partitionlabels分区标签

763.partitionlabels(代码片段)

题目描述：Astring S oflowercaselettersisgiven.Wewanttopartitionthisstringintoasmanypartsaspossiblesothateachletterappearsinatmostonepart,andreturnalistofintegersrepresentingthesizeoftheseparts.&n 查看详情

763.partitionlabels(贪心)(代码片段)

AstringSoflowercaselettersisgiven.Wewanttopartitionthisstringintoasmanypartsaspossiblesothateachletterappearsinatmostonepart,andreturnalistofintegersrepresentingthesizeoftheseparts.Example1:Input:S="a 查看详情

c_cpp763.cpp(代码片段)

查看详情

codeforcesround#763(div.2)editorialc解题报告(代码片段)

763.划分字母区间(代码片段)

方法一：滑动窗口classSolutionpublicList<Integer>partitionLabels(Strings)List<Integer>res=newArrayList<>();int[]arr=newint[128];for(charc:s.toCharArray())arr[c]++;int[]window=newint 查看详情

*leetcode763.partitionlabels(代码片段)

https://leetcode.com/problems/partition-labels/description/constintSIZE=256;classSolutionpublic:booljudge(intcnt[],inthash[])//boolret=true;for(inti=0;i<SIZE;i++)if(hash[i]= 查看详情

763.划分字母区间(代码片段)

字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。示例1：输入：S="ababcbacadefegdehijhklij"输出：[9,7,8]解释：划分结果... 查看详情

763.partitionlabels(代码片段)

Astring S oflowercaselettersisgiven.Wewanttopartitionthisstringintoasmanypartsaspossiblesothateachletterappearsinatmostonepart,andreturnalistofintegersrepresentingthesizeoftheseparts. Example1:Input:S="ababcbacadefegdehijhklij"Output:[9,7,8]Explanation:Thepartitionis"ababcbaca","defeg... 查看详情

cf763b.timofeyandrectangles

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

763.划分字母区间(代码片段)

目录1、Question2、Analysis3、Code4、Result1、Question 字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。示例：输入... 查看详情

[m贪心]lc763.划分字母区间(贪心+代码实现)(代码片段)

文章目录1.题目来源2.题目解析1.题目来源链接：763.划分字母区间2.题目解析lc讨论中看见的华为od面试编程题目，可以试试。贪心思路：本次分割字符串如果在后面都不出现，则单独成一段，作为有效答案。因... 查看详情

codeforcesround#763(div.2)d(推式子+概率)

题目大意：给n*m的矩阵，给机器人起点和垃圾的终点，一开始向右下移动，撞到边界时会反方向移动，当机器人与垃圾同行或者同列时有p/100的概率清理垃圾，求机器人清理掉垃圾的步数期望思路：法... 查看详情

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

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

菜鸟级彩友机选揽大奖旺站中大乐透763万

...票大乐透第16098期开奖，吉林长春一彩民喜获一等奖，将763万元奖金纳入囊中。中得大奖的地址为：长春市西城家园16栋109号门市第02230代销点，当业主庞先生得知本站中了一个一等奖，特别兴奋，随即制作了大喜报及多条条... 查看详情