本番アプローチは良かったが、計算量が落としきれなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13086
問題
0~(N-1)番のN個の頂点からなる2つの木tree1とtree2が与えられる。
tree1上の辺e1とtree2上の辺e2における類似度S(e1,e2)は以下のように定義する。
- e1を切断することでtree1を2つの要素に分割する
- e2を切断することでtree2を2つの要素に分割する
- tree1を分割した要素のうち片方と、tree2を分割した要素のうち片方において、両要素に共通して含まれる頂点番号の数の最大値がS(e1,e2)である。
tree1とtree2の類似度は、tree1,tree2に含まれる各辺e1,e2の対におけるsqr(S(e1,e2))の総和とする。
この値を求めよ。
解法
tree1、tree2を適当な頂点を根とする根付き木と考える。
(便宜上、辺が1つの点を頂点とすると後が考えやすい。)
この時、S(e1,e2)は以下の最大値である。
- tree1においてe1のサブツリー内であり、tree2においてもe2のサブツリー内にある頂点の数
- tree1においてe1のサブツリー内であり、tree2においてはe2のサブツリー外にある頂点の数
- tree1においてe1のサブツリー外であり、tree2においてもe2のサブツリー内にある頂点の数
- tree1においてe1のサブツリー外であり、tree2においてはe2のサブツリー外にある頂点の数
よって(e1,e2)ごとに上記4つの値を求められれば良い。
tree1をDFSで探索し、まずは各辺e1において各頂点のサブツリー内外判定を高速に行いたい。
これにはEuler Tourの結果を用いることができる。
一旦O(N)でEulerTourを行うと、後はO(1)でe1の内外判定が可能。
各e1を固定したうえで、次にtree2をDFSして各e2のサブツリー内外におけるe1サブツリー内の頂点数とe1サブツリー外の頂点数を数え、S(e1,e2)を求めていけばよい。
tree1の各辺ごとにtree2をDFSするので、全体でO(N^2)で処理可能。
vector<int> T[2][4001]; int LL,RR; pair<int,int> memo[4001]; int L[4001],R[4001]; int eid; void EulerTour(int cur,int pre) { if(pre==-1) ZERO(L),ZERO(R),eid=0; L[cur]=eid++; ITR(it,T[0][cur]) if(*it!=pre) EulerTour(*it,cur); R[cur]=eid; } class TreesAnalysis { public: int N,st1; ll ret; pair<int,int> sumsum(int cur,int pre) { int i; if(memo[cur].first!=-1) return memo[cur]; pair<int,int> tot=make_pair(0,0); if(LL<=L[cur] && L[cur]<RR) tot.second++; else tot.first++; FOR(i,T[1][cur].size()) { int tar=T[1][cur][i]; if(tar!=pre) { pair<int,int> pp=sumsum(tar,cur); tot.first+=pp.first; tot.second+=pp.second; } } return memo[cur]=tot; } void dfs1(int cur,int pre) { int i; if(pre!=-1) { LL=L[cur]; RR=R[cur]; FOR(i,N) memo[i].first=-1; sumsum(st1,-1); FOR(i,N) if(i!=st1) { int mama=max(min(max(memo[i].first,N-(RR-LL)-memo[i].first),N-(RR-LL)), min(max(memo[i].second,RR-LL-memo[i].second),RR-LL)); ret += mama*(ll)mama; } } FOR(i,T[0][cur].size()) { int tar=T[0][cur][i]; if(tar!=pre) dfs1(tar,cur); } } long long treeSimilarity(vector <int> tree1, vector <int> tree2) { N=tree1.size()+1; int i; FOR(i,N) T[0][i].clear(); FOR(i,N) T[1][i].clear(); FOR(i,N-1) { T[0][i].push_back(tree1[i]); T[0][tree1[i]].push_back(i); T[1][i].push_back(tree2[i]); T[1][tree2[i]].push_back(i); } FOR(i,N) if(T[1][i].size()==1) st1=i; ret=0; FOR(i,N) if(T[0][i].size()==1) { EulerTour(i,-1); dfs1(i,-1); break; } return ret; } }
まとめ
本番はEulerTourを用いず、サブツリー内外判定をbitmapに持ったためTLEした。