Codeforce 322E Ciel the Commander (点分治)
E. Ciel the Commander
Now Fox Ciel becomes a commander of Tree Land. Tree Land, like its name said, has n cities connected by n - 1 undirected roads, and for any two cities there always exists a path between them.
Fox Ciel needs to assign an officer to each city. Each officer has a rank — a letter from 'A' to 'Z'. So there will be 26 different ranks, and 'A' is the topmost, so 'Z' is the bottommost.
There are enough officers of each rank. But there is a special rule must obey: if x and y are two distinct cities and their officers have the same rank, then on the simple path between x and y there must be a city z that has an officer with higher rank. The rule guarantee that a communications between same rank officers will be monitored by higher rank officer.
Help Ciel to make a valid plan, and if it's impossible, output "Impossible!".
Input
The first line contains an integer n (2 ≤ n ≤ 105) — the number of cities in Tree Land.
Each of the following n - 1 lines contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b) — they mean that there will be an undirected road between a and b. Consider all the cities are numbered from 1 to n.
It guaranteed that the given graph will be a tree.
Output
If there is a valid plane, output n space-separated characters in a line — i-th character is the rank of officer in the city with number i.
Otherwise output "Impossible!".
Examples
Input
4
1 2
1 3
1 4
Output
A B B B
Input
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
Output
D C B A D C B D C D
Note
In the first example, for any two officers of rank 'B', an officer with rank 'A' will be on the path between them. So it is a valid solution.
这个题,我真的不知道什么是点分治。
我们就题论题,这个题说要是点分治我不太懂,但是这个题我的思路很简单。这个题题意是说给一棵树,子节点的级别相同的时父节点的级别一定是高于他们的。开始是这么理解的,但是后来我发现不是这么回事,放两张图大家理解一下。就明白为什么每次都需要找重心了。
一开始我想的是这样:
但是后来我发现如果是这种情况的话:
只有这样才能把节点使用的最少进而达到题目要求。
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=100005;
int vis[maxn],son[maxn],f[maxn],sum,root,ans[maxn];
vector<int> E[maxn];
void dfsroot(int x,int fa)
{
son[x]=1;f[x]=0;
for(int i=0;i<E[x].size();i++)
{
int v = E[x][i];
if(v == fa || vis[v])continue;
dfsroot(v,x);
son[x]+=son[v];
f[x]=max(f[x],son[v]);
}
f[x]=max(f[x],sum-son[x]);
if(f[x]<f[root])root=x;
}//找树的重心
void work(int x,int fa,int dep)
{
ans[x]=dep;
vis[x]=1;
for(int i=0;i<E[x].size();i++)
{
int v = E[x][i];
if(vis[v])continue;
sum=son[v],root=0;
dfsroot(v,x);
work(root,x,dep+1);
}
}//染色
int main()
{
int n;
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
E[x].push_back(y);
E[y].push_back(x);
}
f[0]=sum=n;
dfsroot(1,0);
work(root,0,0);
for(int i=1;i<=n;i++)
printf("%c ",ans[i]+'A');
printf("\n");
return 0;
}
最新文章
- MongoDB基本命令用
- C# 实现 微软WebRequestMethods.Ftp类中的FTP操作功能
- 使用自定义字体 @font-face 小试
- Android将应用程序的崩溃信息如何保存到本地文件,并上传服务器
- 数据结构线性表(js实现)
- word 中Sentences、Paragraph等含义和用法
- innodb结构解析工具---innodb_ruby
- Linq101-Grouping Operators
- UVALive 4123 Glenbow Museum (组合数学)
- mysql处理存在则更新,不存在则插入(多列唯一索引)
- 庆祝POPTEST签约企业培训
- openfire+smack 实现即时通讯基本框架
- android wear开发之:增加可穿戴设备功能到通知中 - Adding Wearable Features to Notifications
- linux常用命令简述
- 配置VLAN
- js screen
- Linux - 用户操作
- cassandra集群缩容与剔除问题节点
- 各种RF的比较
- Js判断出生年月填写的 是否正确