TCO 2015 Round 1B Hard - TheTreeAndMan
問題
TopCoder Statistics - Problem Statement
問題概要
頂点数がの根付き木を考える。そして、全ての辺は根から離れていく方向に向いている(つまり、どの個の頂点にも根からたどり着くことが可能)。頂点をそれぞれ~で番号をふる。の頂点を根とする。また、配列型で各頂点に対して、その頂点の親が何であるかがで与えられる。
そして、Examples内にある図の棒人間みたいな形を"Man"と呼ぶことにする。これは"Man"の中でも最小単位のもので、腕が片方伸びたりしているものも"Man"になる。(7つの頂点組を考え、特定の頂点から特定の頂点へ到達可能(このルートは到達可能なら一意に定まる)であることと、その頂点組を構成した時に辺を共有しないことになる)。
与えられるグラフ内に"Man"がいくつあるかを数え上げて、で割った余りを答えよ。
アイデア
Editorialをみながらまとめる。
まずは、頂点を根とする部分木を考えて、その頂点から到達可能な頂点数をに保存しておく。これは、その親の頂点が自身の頂点より必ず番号が小さいので、番号が大きい方からDP的に埋めていくことが出来る。
そして、次にを計算していきたい。この値の意味するところは、頂点を"Man"の足の付根とするときに、足の2箇所の選び方が何通りあるかという情報を保持する。
まず、これを計算していくために、という値を計算しておく。ここで、は頂点をまさに親として持つ頂点のみを含む(つまり、最初はにはから自身を除いた数が入っている...(?))。そして、これらの各に対して、順に以下のような操作をしていく:
にを加える。これによって、パスが被らないように足の位置を選ぶことが出来る(まだ見ていない自分以外の足の選び方*いま注目している根の下にある中から足を選ぶ方法)
からを除く(の更新)
そして、次にの計算をしていこう。ここには、を頂点とする部分木に含まれる頂点に対してとするものである。これの意味するところは、次で説明する。
最後に、このを固定し、に対して考えていく。頂点の親をとし、をまさに体の中心(頭と腕2本の付け根)とすると、にはを体の中心としたときの足の選び方の総数が入っていると解釈できる。頭の位置の選び方は、頂点の親以上の存在しかなり得ないので、頂点の深さを事前に計算しておけばよいことになる。そして、腕の選び方としては、まず腕の位置を2本決めるのだが、これはまさに脚の決め方と同じであるのでで表される。しかし、脚に到達するパスとは被ってはいけないので、そのような組み合わせを取り除く必要がある。それは、の部分木から1点と、それ以外の部分木から1点を選ぶような組み合わせである。それは、で表される。以上より、
の剰余を計算すれば良い。
最終的に1つの頂点を固定することで計算することがが可能になるのが驚き。後は、腕の計算に脚の前処理をそのまま利用していく方法は感動した。 他にも、体の中心を、足の付根をと固定してからに到達可能であるときに同様に部分木の被りをうまく除きながら掛け算していく方法(で間に合う方法)の方が、直感的にはわかりやすかった。
実装(C++)
class TheTreeAndMan { public: const long mod=1e9+7; int sum(int x, int y) { long ret=x; ret+=y; while(ret<0) ret+=mod; ret%=mod; return (int)ret; } int mul(int x, int y) { long ret=x; ret*=y; ret%=mod; return (int)ret; } int solve(vector<int> parent) { //頂点数 int n=parent.size()+1; //グラフ vector<int> G[2000]; //グラフ内でのその頂点の深さ int depth[2000]={0}; //その頂点から到達可能な頂点数(自身も含む) int reach[2000]={0}; //その頂点を足の付根とするときの選び方の総数 int leg[2000]={0}; //その頂点以下のlegの和 int body[2000]={0}; //有向辺を張る rep(i,parent.size()) G[parent[i]].pb(i+1); //頂点iから到達可能な頂点数を計算 for(int i=n-1; i>=0; --i) { //まず自分自身を計上 reach[i]=1; rep(j,G[i].size()) reach[i]=sum(reach[i],reach[G[i][j]]); } //BFSして深さを計算 queue<int> que; que.push(0); int vis[2000]={0}; vis[0]=1; depth[0]=0; while(!que.empty()) { int v=que.front(); que.pop(); rep(i,G[v].size()) { int nx=G[v][i]; if(!vis[nx]) { vis[nx]=1; depth[nx]=depth[v]+1; que.push(nx); } } } //legの計算 rep(i,n) { int cur=0; rep(j,G[i].size()) cur=sum(cur,reach[G[i][j]]); rep(j,G[i].size()) { leg[i]=sum(leg[i],mul(reach[G[i][j]],sum(cur,-reach[G[i][j]]))); cur=sum(cur,-reach[G[i][j]]); } body[i]=leg[i]; } //bodyの計算 for(int i=n-1; i>0; --i) { body[parent[i-1]]=sum(body[parent[i-1]],body[i]); } int ret=0; for(int i=1; i<n; ++i) { int j=parent[i-1]; int add=mul(depth[i]-1,mul(body[i],sum(leg[j],-mul(reach[i],reach[j]-1-reach[i])))); ret=sum(ret,add); } return ret; } };