Codeforces 781A AndryushaとColored Balloons(樹上のdfs)

1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...

アンドリューシャーと色鉛筆

テストごとの制限時間
2秒

テストごとのメモリ制限
256メガバイト

入力
标准输入

出力
标准输出

Andryushaは毎日公園に通っています。その間にある正方形と道のりはAndryushaには退屈なので、飾ることに決めました。

公園は、( n – 1)の双方向に接続されたn個の正方形で構成されています
Andryushaは各正方形に色のついた風船を掛けることに決めました。風船の色は1から始まる正の整数で表されます。
公園を色彩豊かにするために、Andryushaは特別な方法で色を選択したいと考えています。より正確に言えば、 abc
abが持つ明確な四角
それらの間の直接経路、およびbおよびcは、
これらの3つの正方形の風船の色が異なっています。

Andryushaはできるだけ色の違うものを使いたいと思っています。

入力

最初の行には、単一の整数n (3≤n≤2・105) –
公園の広場の数。

次の( n – 1)行のそれぞれは、2つの整数xy (1≤x、y≤n) –
2つの正方形のインデックスは、パスによって直接接続されています。

どのような四角形にもパスを使用できる他の四角形から到達できることが保証されています。

出力

最初の行では、単一の整数kを印刷します – Andryushaが使用しなければならない最小の色数。

2行目のn個の整数では、 i番目
それらの数は、 i番目の正方形のバルーンの色と同じでなければなりません。これらの数はそれぞれ1からkの範囲内でなければなりません。

入力

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e5+10;
struct node
{
int to,next;
}edge[2*maxn];
int head[2*maxn],ans,n,cnt,a[maxn];
void add(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int x,int y)
{
int num=1,i;
for(i=head[x];i!=-1;i=edge[i].next)
{
if(edge[i].to!=y)
{
while(num==a[x]||num==a[y])
num++;
a[edge[i].to]=num++;
ans=max(ans,num-1);
dfs(edge[i].to,x);
}
}
}
int main()
{
int u,v;
while(scanf("%d",&n)!=EOF)
{
memset(head,-1,sizeof(head));
cnt=0;
for(int i=1;i<n;++i)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
memset(a,0,sizeof(a));
a[1]=1;
ans=0;
dfs(1,-1);
printf("%d\n",ans);
printf("%d",a[1]);
for(int i=2;i<=n;++i)
printf(" %d",a[i]);
printf("\n");
}
return 0;
} 


1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...
      この投稿は審査処理中  | 元のサイトへ