题意
对一棵有 $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