言い換えに気付けばすぐ。
https://atcoder.jp/contests/abc291/tasks/abc291_h
問題
木を成す無向グラフTが与えられる。
Tをもとに、以下を成す根付き木Rを1つ構成せよ。
- 点x,yのR上におけるLCAをzとすると、zはT上でx-yのパス上にある。
- R上で点vのsubtreeのサイズは、vの親頂点のsubtreeの半分以下である。
解法
Tを重心分解していき、分解時の重心を、Rにおいて1手前の重心の子としていけば条件を満たす。
int N; vector<int> E[101010]; int P[101010]; vector<pair<int,int>> Es; int ret[101010]; int vis[101010]; int NV[101010]; int dfs(int cur,int pre) { NV[cur]=1; FORR(e,E[cur]) if(e!=pre && vis[e]==0) NV[cur]+=dfs(e,cur); return NV[cur]; } int dfs2(int cur,int pre,int TNV) { int tot=1; int ok=1; FORR(e,E[cur]) if(e!=pre && vis[e]==0) { int c = dfs2(e,cur,TNV); if(c!=-1) return c; tot += NV[e]; if(NV[e]*2>TNV) ok=0; } if((TNV-tot)*2>TNV) ok=0; if(ok) return cur; return -1; } int split(int cur,int id) { int TNV = dfs(cur,-1); if(TNV==0) return -1; int center=dfs2(cur,-1,TNV); ret[center]=id; vis[center]=1; FORR(e,E[center]) if(vis[e]==0) { P[split(e,id+1)]=center+1; } return center; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } MINUS(P); split(0,0); FOR(i,N) cout<<P[i]<<" "; cout<<endl; }
まとめ
これ重心分解の言い換えじゃん、と気づけるかが鍵。