Centroid Decomposition (min edge on path)

Apr 6th, 2017
550
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import std.stdio;
2. import std.algorithm;
3. import std.typecons;
4. import std.math;
5.
6. alias pair = Tuple!(int, "num", int, "cost");
7.
8. pair[][] g;
9. int[] level, parent;
10. int[][] dp;
11. int n, m;
12.
13. int dfs(int u, int size, ref int center, int prev = -1){
14.     int sum = 1;
15.     foreach(v; g[u])
16.         if (v.num != prev && level[v.num] == -1)
17.             sum += dfs(v.num, size, center, u);
18.     if (center == -1 && (2 * sum >= size || prev == -1)) center = u;
19.     return sum;
20. }
21.
22. void calc(int u, int depth, int dist = int.max, int prev = -1){
23.     dp[depth][u] = dist;
24.     foreach(v; g[u])
25.         if (v.num != prev && level[v.num] == -1)
26.             calc(v.num, depth, min(dist, v.cost), u);
27. }
28.
29. void build(int u, int size, int depth, int prev = -1){
30.     int center = -1;
31.     dfs(u, size, center);
32.     level[center] = depth;
33.     parent[center] = prev;
34.     calc(center, depth);
35.     foreach(v; g[center])
36.         if (level[v.num] == -1)
37.             build(v.num, size / 2, depth + 1, center);
38. }
39.
40. int get_center(int u, int v){
41.     while (level[u] > level[v]) u = parent[u];
42.     while (level[v] > level[u]) v = parent[v];
43.     while (u != v) u = parent[u], v = parent[v];
44.     return u;
45. }
46.
47. int ans(int u, int v){
48.     int ls = get_center(u, v);
49.     return min(dp[level[ls]][u], dp[level[ls]][v]);
50. }
51.
52. void main(){
54.     g = new pair[][n];
55.     dp = new int[][](2 + cast(int)log2(n), n);
56.     level = new int[n + 1];
57.     parent = new int[n];
58.     level[] -= 1;
59.     foreach(i; 1..n){
60.         int u, w;
62.         --u;
63.         g[u] ~= pair(i, w);
64.         g[i] ~= pair(u, w);
65.     }
66.     build(0, n, 0);
68.     foreach(i; 0..m){
69.         int u, v;
71.         writeln(ans(u - 1, v - 1));
72.     }
73. }
RAW Paste Data