Codeforces Codeforces Round #783 (Div. 2)F. Codeforces Round #783 (Div. 2)F
原题链接
困难
作者:
lqmm1
,
2022-04-20 17:19:51
,
所有人可见
,
阅读 295
/*
感觉解释的乱七八糟呜呜呜(修改了好几次,唉就这样吧,摆烂了)
题目意思:一个边周围的边如果数量是偶数那么这个边可以删,反之不能删,给一个树问这个树所有的边能不能删
一个边当前可以删那么这个边我们把他叫做奇边反之叫偶边
那么我们可以发现一个边两侧的点连的边奇偶性一样那么这个边就是奇数边反之是偶数边
删掉一个边后与他相邻的边奇偶性反转
我们思考一下怎么样可以删一颗树
是不是无论什么时候奇数边都等于或比偶数边大一这样可以删
那么假设用1表示当前点对应的边是删到最后可以变成奇数边的点,反之0表示删到最后为偶数边的点
我们让根节点是1,往上构造,如果构造失败那么一定无解
反之构造成功我们思考一下我们能不能得到答案呢?
度为偶数的点1的边等于0边
度为奇数的点1边-1等于0边
首先出了根节点外的点,当前子树的根对应的边一定是1
所有如果当前点的度是奇数我们就从1边中取一个来删,反之从0边取边出来这样就可以构造了
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
#include <vector>
using namespace std;
const int N=2e5+10;
const int M=2*N;
int h[N],ne[M],e[M],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n;
int path[N];
int flag=0;
void dfs(int u,int fa)
{
int cnt[2]={0,0};
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa)continue;
dfs(j,u);
cnt[path[j]]++;
}
if(u!=1)
{
if(cnt[0]>=cnt[1])
{
path[u]=1;
cnt[1]++;
}
else
{
path[u]=0;
cnt[0]++;
}
}
if(cnt[0]>cnt[1]||cnt[1]-cnt[0]>1)
{
flag=1;
}
}
void slove(int u,int fa)
{
vector<int> pa[2];
int cnt=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa&&fa==-1)continue;
cnt++;
if(j==fa)
{
pa[path[u]].push_back(u);
}
else pa[path[j]].push_back(j);
}
int id=cnt%2;
for(int i=1;i<=cnt;i++)
{
int ti=pa[id].back();
if(ti==u)
{
cout << u<<" "<<fa<<endl;
}
else slove(ti,u);
pa[id].pop_back();
id=1-id;
}
}
int main()
{
int t;
cin >> t;
while(t--)
{
flag=0;
cin >> n;
for(int i=1;i<=n;i++)
{
h[i]=-1;
path[i]=0;
}
idx=0;
for(int i=1;i<=n-1;i++)
{
int a,b;
cin >> a>>b;
add(a,b);
add(b,a);
}
dfs(1,-1);
if(flag) cout << "NO"<<endl;
else
{
cout << "YES"<<endl;
slove(1,-1);
}
for(int i=1;i<=n;i++) cout << path[i]<<" ";
cout << endl;
}
return 0;
}
讲的太好了,茅塞顿开
大佬Orz
哈哈solve写成slove是故意的吗?😄
严格鸽也是slove(
我就是学的严格鸽的,哈哈,so love(无端联想)