233
- 题意：
- 分析：
- 代码：
题意：
给出一棵树，我们需要给树上的节点进行编号，使得我们随意删除两种类型的节点时都有叶子节点可供删除并且不影响剩下节点的连通性
分析：
我们直接考虑最极限的情况：一上来就全是早餐，或全是晚餐
那么我们就没必要花里胡哨的了，暴力将一棵树分成两部分，以一条边为界
从两个端点开始往子树里分配编号就好了
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#define LL long long
using namespace std;
inline LL read()
{
LL s=0,f=1; char c=getchar();while(c<'0'||c>'9') {
if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {
s=s*10+c-'0';c=getchar();}return s*f;
}
struct node{
int to,next;
}e[200005];
int ls[200005],cnt=0;
void add(int x,int y)
{
e[cnt]=(node){
y,ls[x]};ls[x]=cnt++;return;
}
int size[100005],s1,s2,n,a,b;
void dfs(int fa,int u)
{
if(s1&&s2) return;size[u]=1;for(int i=ls[u];~i;i=e[i].next){
int v=e[i].to;if(v==fa) continue;dfs(u,v);size[u]+=size[v];}if(size[u]==a) s1=u,s2=fa;if(size[u]==b) s1=fa,s2=u;return;
}
int tf[100005],ans[100005],t;
void get(int u,int p)
{
for(int i=ls[u];~i;i=e[i].next){
int v=e[i].to;if(tf[v]) continue;tf[v]=1;get(v,p);}ans[u]=p*(++t);return;
}
int main()
{
freopen("tom.in","r",stdin);freopen("tom.out","w",stdout);memset(ls,-1,sizeof(ls));n=read(),a=read(),b=read();for(int i=1;i<n;i++){
int x=read(),y=read();add(x,y);add(y,x);}dfs(0,1);if(!s1||!s2) return !printf("-1");tf[s1]=tf[s2]=1;t=0;get(s1,1);t=0;get(s2,-1);for(int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0;
}