Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals) C Andryusha and Colored Balloons
地址:http://codeforces.com/contest/782/problem/C
题目:
2 seconds
256 megabytes
standard input
standard output
Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.
The park consists of n squares connected with (n - 1) bidirectional paths in such a way that any square is reachable from any other using these paths. Andryusha decided to hang a colored balloon at each of the squares. The baloons' colors are described by positive integers, starting from 1. In order to make the park varicolored, Andryusha wants to choose the colors in a special way. More precisely, he wants to use such colors that if a, b and c are distinct squares that a and b have a direct path between them, and b and c have a direct path between them, then balloon colors on these three squares are distinct.
Andryusha wants to use as little different colors as possible. Help him to choose the colors!
The first line contains single integer n (3 ≤ n ≤ 2·105) — the number of squares in the park.
Each of the next (n - 1) lines contains two integers x and y (1 ≤ x, y ≤ n) — the indices of two squares directly connected by a path.
It is guaranteed that any square is reachable from any other using the paths.
In the first line print single integer k — the minimum number of colors Andryusha has to use.
In the second line print n integers, the i-th of them should be equal to the balloon color on the i-th square. Each of these numbers should be within range from 1 to k.
3
2 3
1 3
3
1 3 2
5
2 3
5 3
4 3
1 3
5
1 3 2 5 4
5
2 1
3 2
4 3
5 4
3
1 2 3 1 2
In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct.
Illustration for the first sample.
In the second example there are following triples of consequently connected squares:
- 1 → 3 → 2
- 1 → 3 → 4
- 1 → 3 → 5
- 2 → 3 → 4
- 2 → 3 → 5
- 4 → 3 → 5
We can see that each pair of squares is encountered in some triple, so all colors have to be distinct.
In the third example there are following triples:
- 1 → 2 → 3
- 2 → 3 → 4
- 3 → 4 → 5
We can see that one or two colors is not enough, but there is an answer that uses three colors only.
#include <bits/stdc++.h> using namespace std; #define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-;
const double pi=acos(-1.0);
const int K=2e5+;
const int mod=1e9+; int n,ans,col[K],vis[K];
vector<int>mp[K]; void dfs(int x,int f)
{
for(int i=,t=;i<mp[x].size();i++)
if(mp[x][i]!=f)
{
while(t==col[x]||t==col[f])t++;
col[mp[x][i]]=t++;
}
for(int i=;i<mp[x].size();i++)
if(mp[x][i]!=f)
dfs(mp[x][i],x);
}
int main(void)
{
cin>>n;
for(int i=,x,y;i<n;i++)
scanf("%d%d",&x,&y),mp[x].PB(y),mp[y].PB(x);
col[]=;
dfs(,);
for(int i=;i<=n;i++)
vis[col[i]]=;
for(int i=;i<=n;i++)
ans+=vis[i];
cout<<ans<<endl;
for(int i=;i<=n;i++)
printf("%d ",col[i]);
return ;
}
最新文章
- 【GO】GO语言学习笔记四
- web会话管理
- 【转】本地存储-localStroage/sessionStorage存储
- rabbitmq server的安装以及常用的命令
- [Coursera]Machine Learning
- slidingmenu + fragment 左右菜单滑动
- (转)javascript中 window.location= window.location;是什么意思
- mini KMS Activator v1.3破解激活microsoft Office 2010 RTM
- Bug Tracker
- cocos2d导入iOS原生项目
- 从PyMongo看MongoDB Read Preference
- webpack打包进内联html
- Extjs4.2+webAPI+EF实现分页以及webapi的数据传值
- 索引节点(inode)爆满问题处理
- hdu4942线段树模拟rotate操作+中序遍历 回头再做
- [py]py3/pip/virtualenv/mysql环境安装
- POJ 1679 The Unique MST 【判断最小生成树是否唯一】
- jquery小效果:新浪游戏右侧导航菜单 (页面效果)
- Java常用系统变量收集
- ios开发之--两次模态弹出后,怎么返回最上层的页面