Div2 Hard位の難易度かな?
http://community.topcoder.com/stat?c=problem_statement&pm=13717
問題
N頂点からなる根付木が与えられる。
各辺は親から子に向けた有向辺と見なす。
ここで、以下の条件を満たす7頂点の組の事を人と呼ぶ。
- 1番の点から2番の点に有向辺を辿って到達可能
- 2番の点から3番の点に 〃
- 2番の点から4番の点に 〃
- 2番の点から5番の点に 〃
- 5番の点から6番の点に 〃
- 5番の点から7番の点に 〃
- 上記それぞれの有向辺は互いに重複しない。
図で書くと以下のとおりである。
1 ↓ ↓←2→↓ ↓ ↓ ↓ 3 ↓ 4 ↓ ↓←5→↓ ↓ ↓ 6 7
条件を満たす頂点組の組み合わせ数を求めよ。
解法
まず最初にDFSで以下の処理を行っておく。
- 根からの深さを求める
- 各subtreeにおける頂点数を求めておく。
- EulerTourで頂点に番号付けしておく。
この状態で上図で2・5に相当する点を総当たりする。
まず点5が点2のsubtreeに含まれることをチェックする必要があるが、これはEulerTourの結果で容易に判定できる。
この状態で、残りの頂点の組み合わせ数を算出していく。
これには以下の各要素を掛算すればよい。
- 点1となりうる頂点は、点2の祖先なのでその数は根からの深さに一致する。
- 点3・4となりうる頂点の数は、2→5に至るsubtreeを除き、点2のsubtreeを2つ選択し、両subtreeの頂点数を掛けたものの総和。
- 点6・7となりうる頂点の数は、点5のsubtreeを2つ選択し、両subtreeの頂点数を掛けたものの総和。
以下のコードは、subtreeを2つ求める処理でメモ化を行っていないがそれでも十分間に合っている。
ll mo=1000000007; int PN[2020],D[2020]; vector<pair<int,int> > E[2020]; int L[2020],R[2020],id; class TheTreeAndMan { public: int N; ll pat2(int cur,int exc) { ll ret=0; int tot=0; if(E[cur].size()<2) return 0; FORR(r,E[cur]) { if(exc!=-1 && L[r.first]<=L[exc]&&R[exc]<=R[r.first]) continue; ret += tot*r.second % mo; tot += r.second; } return ret % mo; } int dfs(int cur) { int tot=1; L[cur]=id++; FORR(r,E[cur]) if(r.first>cur) tot += r.second = dfs(r.first); R[cur]=id++; return tot; } int solve(vector <int> parent) { int i,x,y; N=parent.size()+1; FOR(i,N) E[i].clear(); FOR(i,N-1) E[parent[i]].emplace_back(i+1,0), D[i+1]=D[parent[i]]+1; id=0; dfs(0); ll ret=0; FOR(y,N) FOR(x,y) if(L[x]<L[y] && R[y]<R[x]) ret += D[x] * pat2(x,y) % mo * pat2(y,-1) % mo; return ret%mo; } }
まとめ
最近公式Editorialの作成が早くなってきた気がする。