SRM621D1Med TreesAnalysis
こういう系は比較的苦手
問題概要(原文)
$2$ つの $N$ 頂点の木 $T_1, T_2$ がある． $T_1, T_2$ を $e_1, e_2$ でそれぞれ切断した連結成分 $T_{1,a}, T_{1,b}, T_{2,a}, T_{2,b}$ について， $f(e_1,e_2) = max (|T_{1,a} \cap T_{2,a}|,|T_{1,a} \cap T_{2,b}|,|T_{1,b} \cap T_{2,a}|, |T_{1,b} \cap T_{2,b}|)$ とする．
$g(e_1,e_2) = f(e_1,e_2)^2$ とする． $e1,e2$ を全てのペア試したときの $g(e_1,e_2)$ の総和を求めよ．
考察
$O(N^3)$ で全て網羅できるが，これだと間に合わない．
ここで，$T_1,T_2$ をそれぞれ頂点 $0$ を根とする根付き木として考える． $T_1$ について行きがけ順で番号を割り振ると，ある頂点を根とする部分木かどうかを区間で表すことができるようになり， $O(1)$ で部分木の内外判定が可能になる．
$e_1$ を固定して考える．ある頂点 $v$ が子孫側の頂点 $u$ を根とする部分木に含まれるかどうかは $[ordl_u, ordr_u)$ に $v$ が含まれるかどうかで判定できる． $T_2$ についてdfsをして，ある辺の子孫側の頂点 $v$ を根とする部分木 $T_2^{\prime}$に， $u$ を根とする部分木 $T_1^{\prime}$に含まれる頂点の数 $x$ を調べることができる．
ここで $f(e_1,e_2) = max (x, size_v - x, size_u -x, n-x-(size_v-x)-(size_u-x))$ が成立する．
このようにして，全探索が可能である． $O(N^2)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class TreesAnalysis
{
public long treeSimilarity(int[] tree1, int[] tree2)
{
var n = tree1.Length + 1;
var G = Enumerate(2, x => Enumerate(n, y => new List<int>()));
for (int i = 0; i < n - 1; i++)
{
G[0][i].Add(tree1[i]);
G[0][tree1[i]].Add(i);
G[1][i].Add(tree2[i]);
G[1][tree2[i]].Add(i);
}
int[] ordl = new int[n], ordr = new int[n], size = new int[n];
{
var ptr = 0;
dfs(-1, 0, G[0], ref ptr, ordl, ordr, size);
}
long ans = 0;
for (int e1 = 0; e1 < n - 1; e1++)
{
var u = e1;
if (ordl[u] < ordl[tree1[e1]]) u = tree1[e1];
var l = ordl[u]; var r = ordr[u];
Func<int, int, KeyValuePair<int, int>> efs = null;
efs = (prev, cur) =>
{
var ret = 0;
var sz = 1;
if (l <= ordl[cur] && ordl[cur] < r) ret++;
foreach (var to in G[1][cur])
{
if (to == prev) continue;
var res = efs(cur, to);
var a = res.Key;
var b = res.Value - res.Key;
var c = size[u] - res.Key;
var d = n - a - b - c;
var max = Math.Max(a, b);
max = Math.Max(max, Math.Max(c, d));
ans += max * max;
ret += res.Key;
sz += res.Value;
}
return new KeyValuePair<int, int>(ret, sz);
};
efs(-1, 0);
}
return ans;
}
int dfs(int prev, int cur, List<int>[] G, ref int ptr, int[] ordl, int[] ordr, int[] size)
{
var ret = 1;
ordl[cur] = ptr++;
foreach (var to in G[cur])
{
if (prev == to) continue;
ret += dfs(cur, to, G, ref ptr, ordl, ordr, size);
}
ordr[cur] = ptr++;
return size[cur] = ret;
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}
コメント
- いまだにオイラーツアーをする系はちょっと不得意
