首页 > 代码库 > AIM Tech Round 3 (Div. 2) E. Centroids
AIM Tech Round 3 (Div. 2) E. Centroids
题解:
树形dp
非常好的一道题目
题意:
对于每个点。更改一条边,能否使得这个点成为树的重心
题解:
所谓重心:指去掉这个点后,最大的连通分量的点数<=n/2
对于每个点,分为向下分析,向上分析
向下分析:找寻点u的子节点的最大节点v。然后找寻节点v的子节点的小于等于n/2的最大子节点,连接到u上
向上分析:找寻点u的父节点的最大节点v。如果v==u那么。找寻次大节点w。然后找寻该点的子节点的小于等于n/2的最大子节点,连接到u上
向下分析和向上分析只需要判断一个,因为大于n/2的点只有一个
代码参考:http://blog.csdn.net/u014258433/article/details/52454105?locationNum=9
代码:
#include<bits/stdc++.h> #define maxn 400010 #define mod 1000000007 #define ll long long #define pb push_back #define fs first #define se second using namespace std; const int INF=1e9+7; int n; vector<int> G[maxn]; int fson[maxn],sson[maxn],up[maxn],dw[maxn]; int siz[maxn],ans[maxn]; void dfs(int u,int fa) { siz[u]=1; fson[u]=sson[u]=0; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(v==fa) continue; dfs(v,u); siz[u]+=siz[v]; if(dw[v]>sson[u]) sson[u]=dw[v]; if(fson[u]<sson[u]) swap(fson[u],sson[u]); } dw[u]=fson[u]; if(siz[u]<=n/2) dw[u]=siz[u]; } void dfs1(int u,int fa) { if(fa!=-1) { up[u]=max(up[u],up[fa]); if(dw[u]!=fson[fa]) up[u]=max(up[u],fson[fa]); else up[u]=max(up[u],sson[fa]); if(n-siz[u]<=n/2) up[u]=n-siz[u]; } int tmp=0; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(v==fa) continue; dfs1(v,u); if(siz[v]>n/2) tmp=v; } if(n-siz[u]>n/2) tmp=-1; if(!tmp) ans[u]=1; else if(tmp>0) { if(siz[tmp]-dw[tmp]<=n/2) ans[u]=1; } else if(n-siz[u]-up[u]<=n/2) ans[u]=1; } int main() { cin>>n; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; G[x].pb(y); G[y].pb(x); } dfs(1,-1); dfs1(1,-1); for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf("\n"); return 0; }
AIM Tech Round 3 (Div. 2) E. Centroids
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。