2014-05-23

SRM 621 Div1 500 TreesAnalysis

21:07 |

頂点 0〜N-1 を持つ木が2つ与えられる。それぞれの木から1辺ずつ(e1, e2)選んで消すとそれぞれの木は2つの部分に分かれる。
それぞれの木からどちらかの部分を選んだ時、どちらの部分にも含まれる頂点ラベルの個数^2の最大値をS(e1, e2)とする。
全ての辺に対して S(e1, e2) の和を求めよ。2≦頂点数≦4000

ファッ！？
なんてややこしいんだ
シミュレーションを書いてみる
それぞれの辺に対して頂点→片方の部分に含まれるかどうか bitset<4000> に持っておいて
全ての e1, e2 について bitset の and, ~and, and~, ~and~ のbitを数える
O(N^2)だけど定数項が大きいのでだめそう
それしか思いつかないので提出 → challenge phase なぜか生き残る → failed system test

(あとで)

＼ touristさんのを見て学ぼうコーナー／
http://community.topcoder.com/stat?c=problem_solution&rm=322260&rd=15854&pm=13086&cr=22263204

■ ポイント1

0 を根だとして、頂点 n1 in Tree1, n2 in Tree2 に対して
「n1 以下(n1とその子孫)の頂点ラベル集合 ∩ n2 以下の頂点ラベル集合」の個数 Xect[n1][n2] と
n1 以下の頂点の個数 size[木][n1] がわかっていれば答えが求まる

|n1以下の集合 ∩ n2以下の集合| = Xect[n1][n2]
|n1以下の集合以外 ∩ n2以下の集合| = size[Tree2][n2] - Xect[n1][n2]
|n1以下の集合 ∩ n2以下の集合以外| = size[Tree1][n1] - Xect[n1][n2]
|n1以下の集合以外 ∩ n2以下の集合以外| = (N - size[Tree1][n1]) - (size[Tree2][n2] - Xect[n1][n2])

n1以下以外  n2以下以外
 0 1 2      2 3 
n1以下     n2以下
 3 4        0 1 4

のとき Xect[n1][n2] = |{4}| = 1
n1以下以外 ∩ n2以下 は?
→ 0 1 4 のうち 4 は Xect に入ってるので n1 以下にあるので "n1以下以外 ∩ n2以下" には含まれない。
→ それ以外の 0 1 は n1 以下にはないはずなので n1 以下以外にあるはず→つまり n1以下以外 ∩ n2以下 に含まれる
なので size[Tree2][n2] - Xect[n1][n2]

まずこれが思いつかんのだなこれが。
size は dfs で求まる

■ ポイント2

Xect も size みたいに葉→根に足していって求められる。
まず初期状態として、n1 n2 に対して {n1}の頂点ラベル集合 ∩ {n2}の頂点ラベル集合 = XectNodeNode[n1][n2] を考える。
これは同じかどうかなので XectNodeNode[n1][n2] = n1==n2

n1以下の頂点ラベル集合 ∩ {n2}の頂点ラベル集合 = XectTreeNode[n1][n2] を求めるために Tree1 を dfs する。
XectTreeNode ← XectNodeNode として
帰りがけ順に XectTreeNode[node][i] += XectTreeNode[child][i] for i in [0, N), Tree1 に node-childの辺がある

次に Tree2 視点にするために XectNodeTree ← XectTreeNode の転置として
n1以下の頂点ラベル集合 ∩ n2以下の頂点ラベル集合 = Xect を求めるために Tree2 を dfs
Xect ← XectNodeTree としておいて
帰りがけ順に Xect[node][i] += Xect[child][i] for i in [0, N), Tree2 に node-childの辺がある

最後、すべての辺に対してその辺が分断するノードの片方をもれなく列挙するとこも微妙に悩ましいが、
0 を根としたのだから 0 以外の頂点は必ず親を持つ
→ 0 以外の頂点 i すべてについて i とその親を結ぶ辺を列挙すれば MECE になるので頂点 [1, N)x[1, N) を全部見ればよい。

全体で O(N^2)

accepted in practice room
ふむふむほうほう
ちなみに tourist さんは 13 分 30 秒で解いています。( ﾟдﾟ)

// 理解した後に書いたコード　（ほぼそのままですね
class TreesAnalysis {
public:
	void dfs(int t, int idx, int prev, vector<VVI>& g, VVI& size, VVI& xect) {
		int N = xect.size();
		size[t][idx]=1;
		REP(i, g[t][idx].size()) {
			int ci=g[t][idx][i];
			if(ci==prev) continue;
			dfs(t, ci, idx, g, size, xect);
			size[t][idx]+=size[t][ci];
			REP(j, N) xect[idx][j]+=xect[ci][j];
		}
	}
	long long treeSimilarity(vector <int> T1, vector <int> T2) {
		int N=T1.size()+1;
		vector<VVI> g(2, VVI(N));
		VVI size(2, VI(N));
		VVI xect(N, VI(N));
		REP(t, 2) REP(i, N-1) {
			int j=(t==0?T1:T2)[i];
			g[t][i].PB(j);
			g[t][j].PB(i);
		}
		REP(i, N) xect[i][i]=1;
		REP(t, 2) {
			dfs(t, 0, -1, g, size, xect);
			REP(i, N) RANGE(j, i+1, N) swap(xect[i][j], xect[j][i]);
		}
		ll ans = 0;
		RANGE(i, 1, N) RANGE(j, 1, N) {
			int x=xect[i][j];
			int a=size[0][i];
			int b=size[1][j];
			ll add = max(x, max(a-x, max(b-x, N-a-(b-x))));
			ans += add*add;
		}
		return ans;
	}
};

kojingharangの日記

2014-05-23

SRM 621 Div1 500 TreesAnalysis