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番の点に 〃
- 上記それぞれの有向辺は互いに重複しない。
図で書くと以下のとおりである。
１ ↓ ↓←２→↓ ↓ ↓ ↓ ３ ↓ ４ ↓ ↓←５→↓ ↓ ↓ ６ ７
条件を満たす頂点組の組み合わせ数を求めよ。
解法
まず最初にDFSで以下の処理を行っておく。
- 根からの深さを求める
- 各subtreeにおける頂点数を求めておく。
- EulerTourで頂点に番号付けしておく。
この状態で上図で２・５に相当する点を総当たりする。
まず点５が点２のsubtreeに含まれることをチェックする必要があるが、これはEulerTourの結果で容易に判定できる。
この状態で、残りの頂点の組み合わせ数を算出していく。
これには以下の各要素を掛算すればよい。
- 点１となりうる頂点は、点２の祖先なのでその数は根からの深さに一致する。
- 点３・４となりうる頂点の数は、２→５に至るsubtreeを除き、点２のsubtreeを2つ選択し、両subtreeの頂点数を掛けたものの総和。
- 点６・７となりうる頂点の数は、点５の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の作成が早くなってきた気がする。
