首页 > 其他分享 >[ABC126D] Even Relation 题解

[ABC126D] Even Relation 题解

时间:2024-06-07 19:56:32浏览次数:20  
标签:Even cnt color 题解 ll head dfs edge Relation

题意

对一棵有 $N$ 个点,$N-1$ 条边的树进行黑白染色,使得每两个距离为偶数的点颜色都一致。

思路

首先让我们回顾一下加法的性质:

  • 偶 $+$ 偶 $=$ 偶
  • 奇 $+$ 奇 $=$ 偶
  • 偶 $+$ 奇 $=$ 奇

不难看出,距离为偶数的关系是可以传递的,而距离为奇数的关系不行。

我们只需要做一遍 dfs,对一个点 $x$ 的邻接点中距离 $x$ 为偶数的点染成与 $x$ 相同的颜色,否则染成另外一种颜色,便可通过此题。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,s,d[100005],f;
ll ans;
ll head[200005],cnt=1;
ll color[100005];
bool flag[100005];
struct node{
    ll to,next,val;
}edge[200005];
void add(ll x,ll y,ll z){
    edge[cnt].to=y;
    edge[cnt].val=z;
    edge[cnt].next=head[x];
    head[x]=cnt++;
}
void dfs(ll x){
    flag[x]=1;
    for(int i=head[x];i;i=edge[i].next){
        ll u=edge[i].to;
        if(flag[u]){
            continue;
        }
        if(edge[i].val%2==0){
            color[u]=color[x];
            dfs(u);
        }
        else{
            color[u]=!color[x];
            dfs(u);
        }
    }
}
int main(){
    scanf("%lld",&a);
    for(int i=1;i<=a-1;i++){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1);
    for(int i=1;i<=a;i++){
        printf("%lld\n",color[i]);
    }
    return 0;
}

标签:Even,cnt,color,题解,ll,head,dfs,edge,Relation
From: https://www.cnblogs.com/PerchLootie/p/18237783

相关文章

  • [ABC191E] Come Back Quickly 题解
    题面:给你一个$n$个点$m$条边的有向图,第$i$条边$a_i$,$b_i$,$c_i$,表示一条单向边从$a_i$到$b_i$,长度为$c_i$,可能会有重边和自环。问能否从第$i$号点出发然后回到该点形成一个环?可以则输出最短时间,否则输出$-1$。思路:不难发现本题考查的是最短路。观察题面,发现边数......
  • [ABC126F] XOR Matching 题解
    很好的构造题。题意请构造一个长度为$2^{m+1}$的序列$a$,该序列满足:$\foralli\in[1,2^{m+1}],a_i\in[0,2^m-1]$且每个数都恰好出现两次。对于任意一对$(i,j)$满足$a_i=a_j$,$a_i\oplusa_{i+1}\oplus\cdots\oplusa_{j-1}\oplusa_j=k$。$\oplus$表......
  • Prism之EventAggregator——实现ViewModel之间传递数据的工作
    publicclassMessageViewModel:BindableBase{IEventAggregator_ea;privatestring_message="MessagetoSend";publicstringMessage{get{return_message;}set{SetProperty(ref_message,value);}}......
  • 食物链题解
    由题得,所有动物整体关系如上。起初每个动物相互时间没有关系,bb[i]=i。对于x与y:如果它们是同类即x到y的距离为$0$,或者转了几圈,一圈距离为$3$,即模$3$余$0$。如果x捕食y,就是x到y距离模$3$余$1$。对x与y操作时:如果它们没有关系(它们不被之前给出的某......
  • 题解:ABC270G Sequence in mod P
    题目传送门思路题目给出了一个数列\[x_{i+1}\equiv{a\timesx_i+b}\pmod{p}\]并想要求最小的\(x_i=G\),那我们可以考虑求出这个数列的通项公式。具体的,观察到原式可以转化成一个等比数列的形式,所以我们可以先设一个常数\(k\),使得\[x_{i+1}+k=a(x_i+k)\]替换进原先的式子......
  • codeforces round 961题解(A、B、C)
    A.GuesstheMaximum因为\(i<j\),所以所有的\([i,j]\)区间中都至少包含两个相邻元素,所以只要求出所有相邻元素中较大值的最小值即可。intn;inta[N];voidsolve(){cin>>n;intmin_v=1e9+1;for(inti=1;i<=n;i++){cin>>a[i];......
  • 怎么发送超大文件?困扰已久的邮件大附件发送问题解决了!
    邮件是日常中使用最多的文件流转工具,特别是对于企业内部的员工间、及企业与企业间的业务开展,数据和文件的发送、业务留痕大多都基于邮箱展开。邮箱的普遍使用给用户基于邮箱进行业务沟通提供了前提,其中,Outlook邮箱是使用最广泛的邮箱之一。这使得邮箱成为一种最常用的通讯工具,但......
  • LCTF 2018 bestphp‘s revenge
    考点:Soap原生类+Session反序列化+CRLF注入<?phphighlight_file(__FILE__);$b='implode';call_user_func($_GET['f'],$_POST);session_start();if(isset($_GET['name'])){$_SESSION['name']=$_GET['name......
  • 6月6日模拟赛题解
    P4315月下“毛景树”没代码能力,写不动,赛时没写。注意pushdown即可。#include<bits/stdc++.h>inlineintread(){ charch=getchar();intx=0,f=1; for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1; for(;ch>='0'&&ch<......
  • JavaScript-event
    JavaScript-eventHTML事件是发生在HTML元素上的“事情”,例如:按钮被点击鼠标移到元素上输入框失去焦点事件的绑定方式一:通过html标签中的事件属性进行绑定<inputtype="button"value="事件按钮"onclick="on()"><script> functionon(){ alert("按钮1被点击了..."......