kmjp's blog

競技プログラミング参加記です

TopCoder SRM 621 Div1 Medium TreesAnalysis

本番アプローチは良かったが、計算量が落としきれなかった。
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した。