codeforces 709E E. Centroids(树形dp)
题目链接:
4 seconds
512 megabytes
standard input
standard output
Tree is a connected acyclic graph. Suppose you are given a tree consisting of n vertices. The vertex of this tree is called centroid if the size of each connected component that appears if this vertex is removed from the tree doesn't exceed .
You are given a tree of size n and can perform no more than one edge replacement. Edge replacement is the operation of removing one edge from the tree (without deleting incident vertices) and inserting one new edge (without adding new vertices) in such a way that the graph remains a tree. For each vertex you have to determine if it's possible to make it centroid by performing no more than one edge replacement.
The first line of the input contains an integer n (2 ≤ n ≤ 400 000) — the number of vertices in the tree. Each of the next n - 1 lines contains a pair of vertex indices ui and vi (1 ≤ ui, vi ≤ n) — endpoints of the corresponding edge.
Print n integers. The i-th of them should be equal to 1 if the i-th vertex can be made centroid by replacing no more than one edge, and should be equal to 0 otherwise.
3
1 2
2 3
1 1 1
5
1 2
1 3
1 4
1 5
1 0 0 0 0 题意: 给出一棵树,要求你最多改变一条边,看这个点能否成为重心; 思路: 树形dp,先转化成有根树,第一次dfs先找到每个节点以下的节点数目和能切断的最多的数目以及最多和次多转移来的节点,第二次dfs就是找答案了;
由于一个那个超过n/2的子树只有一棵,要么来自当前节点的子节点,要么来自父节点,所以在树上进行转移;具体的看代码注释; AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
if(!p) { puts("0"); return; }
while(p) stk[++ tp] = p%10, p/=10;
while(tp) putchar(stk[tp--] + '0');
putchar('\n');
} const LL mod=1e9+7;
const double PI=acos(-1.0);
const int inf=1e9;
const int N=4e5+10;
const int maxn=1e3+20;
const double eps=1e-12; int n,siz[N],ans[N],submax[N],max1[N],max2[N];
vector<int>ve[N]; void dfs(int cur,int fa)
{
siz[cur]=1;//节点数目
submax[cur]=0;//submax[cur]是以cur为根的子树能切掉的最大的节点数目,
int len=ve[cur].size();
for(int i=0;i<len;i++)
{
int x=ve[cur][i];
if(x==fa)continue;
dfs(x,cur);
siz[cur]+=siz[x];
if(submax[x]>submax[cur])
{
max2[cur]=max1[cur];//max2[cur]记录次大,max1[cur]记录最大;
max1[cur]=x;
submax[cur]=submax[x];
}
else if(submax[x]>submax[max2[cur]])max2[cur]=x;
}
if(siz[cur]<=n/2)submax[cur]=siz[cur];
}
void dfs1(int cur,int fa,int mmax)
{
int len=ve[cur].size(),flag=1;
for(int i=0;i<len;i++)
{
int x=ve[cur][i];
if(x==fa)//父节点转移过来
{
int temp=n-siz[cur];
if(temp>n/2&&temp-mmax>n/2)flag=0;
continue;
}
if(siz[x]>n/2)//子节点转移过来
{
if(siz[x]-submax[x]>n/2)flag=0;
}
}
ans[cur]=flag;
for(int i=0;i<len;i++)
{
int x=ve[cur][i];
if(x==fa)continue;
int temp;
if(n-siz[x]<=n/2)temp=n-siz[x];
else
{
if(max1[cur]==x)temp=max(mmax,submax[max2[cur]]);//如果x正好是最大的转移过来的就取mmax和次大的最大值
else temp=max(mmax,submax[max1[cur]]);//否则取mmax与最大的最大值
}
dfs1(x,cur,temp);
}
}
int main()
{
read(n);
int u,v;
For(i,1,n-1)
{
read(u);read(v);
ve[v].push_back(u);
ve[u].push_back(v);
}
dfs(1,0);
dfs1(1,0,0);
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}
最新文章
- 【原创】Kafka producer原理 (Scala版同步producer)
- Spring Boot中静态资源(JS, 图片)等应该放在什么位置
- (转)Javascript本地存储小结
- mysql大表myisam的导入
- Spark Streaming资源动态申请和动态控制消费速率剖析
- Web应用工作流程总结
- [BZOJ 2007] [Noi2010] 海拔 【平面图最小割(对偶图最短路)】
- 2、elasticsearch 的安装和插件的安装
- CentOS启动报错:Centos kernel panic-not syncing:VFS:Unable to mount root fs on unknown block
- linux 下安装mysql
- Redis MSET的极限在哪里
- 2017-4-25/设计缓存(LFU)
- Javascript实现继承
- python2.7入门---变量类型
- 离线下载安装 NLTK 的 nltk_data 模块
- 使用Apache下poi创建和读取excel文件
- 最经典的常用拍照姿势大全,顶级POSE
- TQ2440与西门子S7-200 PLC自由口通信实现过程中问题总结
- hive sequencefile导入文件遇到FAILED: SemanticException Unable to load data to destination table. Error: The file that you are trying to load does not match the file format of the destination table.错误
- (转)用Python写堡垒机项目