[CF708C]Centroids

概述Centroids 题目大意 一棵树，对于每个点，我们删掉任意一条边，再连上任意一条边，求这样 *** 作后可以使这个点为重心的点数 范围\(n\)级别 Solution 嗯，首先对于一个点\(u\)，若全部子树（包括自己头上的那一堆）都不到总点数\(n\)的一半的肯定符合条件 然后若\(u\)的子树\(\{ v \}\)中有一个点数\(> {n \over 2}\)的\(v1\)，我们要在这样的子树中找 CentroIDs 题目大意

一棵树，对于每个点，我们删掉任意一条边，再连上任意一条边，求这样 *** 作后可以使这个点为重心的点数

范围\(n\)@H_502_14@级别

Solution

嗯，首先对于一个点\(u\)@H_502_14@，若全部子树（包括自己头上的那一堆）都不到总点数\(n\)@H_502_14@的一半的肯定符合条件

然后若\(u\)@H_502_14@的子树\(\{ v \}\)@H_502_14@中有一个点数\(> {n \over 2}\)@H_502_14@的\(v1\)@H_502_14@，我们要在这样的子树中找到最大的一棵点数\(<= {n \over 2}\)@H_502_14@的子树 \(v2\)@H_502_14@。

把它断开来，然后把\(v2\)@H_502_14@连上\(u\)@H_502_14@，如果这样后\(v1\)@H_502_14@点数\(<= {n \over 2}\)@H_502_14@，就满足条件

然后用树形DP的老思想：先处理出子树的，再利用子树信息搞一搞头上的就可以了。

code:

#include<bits/stdc++.h>using namespace std;struct qwq{    int v;    int nxt;}edge[800010];int cnt=-1;int head[400010];voID add(int u,int v){    edge[++cnt].nxt=head[u];    edge[cnt].v=v;    head[u]=cnt;}int fir[400010],sec[400010];voID up_max(int &x,int &y,int val){    if(val>x){y=x;x=val;return;}    else if(val>y){y=val;return;}    else return;}int n;int siz[400010];int usiz[400010];int g[400010];voID dfs(int u,int fa){    siz[u]=1;    for(int i=head[u];~i;i=edge[i].nxt){        int v=edge[i].v;        if(v==fa)continue;        dfs(v,u);        siz[u]+=siz[v];        if(siz[v]>n/2)g[u]=v;        if(siz[v]<=n/2)up_max(fir[u],sec[u],siz[v]);        else up_max(fir[u],fir[v]);    }    usiz[u]=n-siz[u];    if(usiz[u]>n/2)g[u]=-1;}int um[400010];voID dfs2(int u,int fa){    if(usiz[u]<=n/2){        um[u]=usiz[u];    }    else if(fir[fa]==siz[u]){        um[u]=max(um[fa],sec[u]);    }    else {        um[u]=max(um[fa],fir[fa]);    }    for(int i=head[u];~i;i=edge[i].nxt){        int v=edge[i].v;        if(v==fa)continue;        dfs2(v,u);    }}bool ans[400010];int main(){    memset(head,-1,sizeof(head));    scanf("%d",&n);    for(int i=1;i<n;++i){        int u,v;        scanf("%d%d",&u,&v);        add(u,v),add(v,u);    }    dfs(1,0);    dfs2(1,0);    for(int i=1;i<=n;++i){        if((!g[i])||(g[i]==-1&&usiz[i]-um[i]<=n/2)||(g[i]!=-1&&siz[g[i]]-fir[g[i]]<=n/2))ans[i]=true;    }    for(int i=1;i<=n;++i){        printf("%d ",ans[i]);    }}

总结

以上是内存溢出为你收集整理的[CF708C]Centroids全部内容，希望文章能够帮你解决[CF708C]Centroids所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。