Codeforces G. Ciel the Commander
题目描述:
Ciel the Commander
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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
Copy
4
1 2
1 3
1 4
Output
Copy
A B B B
Input
Copy
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
Output
Copy
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.
思路:
题目是给一个树,在树上的节点标号,要求是两个相同标号的连通的路径上必须有一个比他们等级高的标号。
刚开始时,这样想的:画了一幅图(很简单的),我把度数为一的标号为'Z',删掉这些点,又出现了度数唯一的点,标为'Y',再删掉,这样每次标记度数为一的点然后删到最后只剩两个点再特殊处理一下,如果这个过程中出现了字母用完的情况就说明不可能。但是这样做有个问题,其实字母用完了还是有可能继续完成标号的,我又改为字母用完了有倒序从'B'到'Z'标号,这样倒过来倒过去,还是错了,_(:з」∠)__
真正的做法是每次找树的重心,在重心处标号,根据重心定义(当前所有节点中最大的子树最小的节点),重心的最大子树的大小不会超过重心所在子树的一半。如果树退化成一条链,可以标记的节点数为\(1+2+4+...+2^{25}=2^{26}\)个节点,远远多于题目的限制。如果树不退化成链,那么可标记的点更多。因此必有解。
注意的是divide函数里面下一次divide是\(rt\)而不是\(v\)啊,血的教训啊w(゚Д゚)w,不是找的重心当然会把标记用光。
代码:
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define max_n 200005
using namespace std;
int n;//n为节点数
char ans[max_n];
//链式前向星
int cnt = 0;
int head[max_n];
struct edge
{
int v;
int nxt;
}e[max_n<<1];
void add(int u,int v)
{
++cnt;
e[cnt].v=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int rt,ms;//rt为重心,ms是最小 最大子树的大小
int Size;//当前整棵树的大小
int sz[max_n];//sz[i]表示以i为根的子树大小
int mson[max_n];//mson[i]表示以i的最大子树的大小
bool visit[max_n];//标记是否分治过
//求重心函数
void get_root(int u,int from)
{
sz[u]=1;mson[u]=0;//开始时以u为根的子树大小为1,u的最大子树为0
for(int i=head[u];i;i=e[i].nxt)//遍历与u相连边
{
int v=e[i].v;
if(visit[v]||v==from) continue;//防止重复遍历
get_root(v,u);
sz[u]+=sz[v];//更新以u为根的子树大小
mson[u]=max(mson[u],sz[v]);//更新u的最大子树
}
if(Size-sz[u]>mson[u]) mson[u]=Size-sz[u];//看是否另一半子树更大
if(ms>mson[u]) ms=mson[u],rt=u;//更新最小的最大子树和重心
}
//求解答案函数
//分函数
void divide(int u,int ssize,int ch)
{
visit[u]=true;//当前节点已分治
ans[u] = ch;
for(int i = head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(visit[v]) continue;//已分治过的不用再分治
ms=INF;rt=0;//每一次求重心都要初始化这两个值
Size=sz[v]<sz[u]?sz[v]:ssize-sz[u];
get_root(v,0);//求出子树的重心
divide(rt,Size,ch+1);//分治子树
}
}
int main()
{
cin >> n;
for(int i = 1;i<n;i++)
{
int u,v;
cin >> u >> v;
add(u,v);
add(v,u);
}
Size=n;//开始为n整棵树大小
rt=0;ms=INF;
get_root(1,0);
/*for(int i = 1;i<=n;i++)
{
cout << "sz " << sz[i] << " mson " << mson[i] << endl;
}
cout << "rt " << rt << endl;*/
divide(rt,n,0);
for(int i = 1;i<=n;i++)
{
char chr = ans[i]+'A';
cout << chr << " ";
}
cout << endl;
return 0;
}
参考文章:
九野的博客,Codeforces 321C Ciel the Commander 树分治,https://blog.csdn.net/acmmmm/article/details/46931215
最新文章
- 数组操作splice
- Apache Tomcat开机后台启动
- SQL Server附加数据库出现错误5123的正确解决方法
- Dom初
- POJ3680_Intervals
- javascript-如何判断一个对象为数组
- iOS - UITableViewController
- N.O.W,O.R,N.E.V.E.R--12days to LNOI2015
- bootstrap 响应式布局 居中问题
- Solr(四)Solr实现简单的类似百度搜索高亮功能-1.配置Ik分词器
- 【转】HTTP Header 详解
- tar --打包和压缩
- Java框架之Mybatis(一)
- UNIX网络编程——UDP回射服务器程序(初级版本)以及漏洞分析
- GoJS学习笔记
- Asp.Net 之 Web.config 配置文件详解
- thymeleaf-extras-db 0.0.1发布,select标签加载数据的新姿势
- Elasticsearch之中文分词器插件es-ik的自定义词库
- Python 单例模式讲解
- AppFog使用
热门文章
- 【DL基础】GridSearch网格搜索
- flutter本地环境的安装以及编辑器的配置
- Anaconda3配置多版本python环境开发
- SpringBoot+Vue前后端分离项目,maven package自动打包整合
- Nginx为什么可以支持高并发
- Java 将 PPT 形状(表格、文本框、心形、图表等)保存成图片
- C++用new与不用new创建对象的区别
- matlab界面UI设计资料
- 解决clover配置文件conf.plist中nv_disable=1或者nvda_drv=1不生效或者说不能删除的问题
- Java字节码扩展