﻿ heavy path decomposition

# heavy path decomposition

## 計算量

$O(n)$ (heavy path decomposition単体の計算量)

## 使い方

public HLDecomposition(int n)

void ae(int a, int b)

void pre()
heavy path decompositonを行います。
int[] heavy

void setVal(int k, int val)

long output(int a, int b, HLDecomposition hl, SegmentTree st)
heavy path decompositionがhl,頂点の重みがstで与えられるような木について、頂点a,b間のパスに含まれる頂点の重みのうち最大のものをreturnします。
int lca(int u, int v)

## ソースコード

long output(int a, int b, HLDecomposition hl, SegmentTree st) {
long ea = -1;
long eb = -1;
int tmp = a;
a = b;
b = tmp;
long tmp_e = ea;
ea = eb;
eb = tmp_e;
}
ea = merge(st.query(hl.id[hl.head[a]], hl.id[a] + 1), ea);
}
if (hl.depth[a] < hl.depth[b]) {
int tmp = a;
a = b;
b = tmp;
long tmp_e = ea;
ea = eb;
eb = tmp_e;
}
return merge(eb, merge(st.query(hl.id[b], hl.id[a] + 1), ea));
}

long merge(long a, long b) {
return Math.max(a, b);
}

class SegmentTree {
int n;
long[] Vs;

public SegmentTree(int n_) {
n = 1;
while (n < n_) {
n *= 2;
}
Vs = new long[2 * n - 1];
for (int i = 0; i < n; ++i) {
Vs[i + n - 1] = -1;
}
for (int i = n - 2; i >= 0; --i) {
Vs[i] = merge(Vs[2 * i + 1], Vs[2 * i + 2]);
}
}

void setVal(int k, long val) {
k += n - 1;
if (val != -1)
Vs[k] = val;
else
Vs[k] = -1;
while (k > 0) {
k = (k - 1) / 2;
Vs[k] = merge(Vs[2 * k + 1], Vs[2 * k + 2]);
}
}

long query(int a, int b) {
return query(a, b, 0, n, 0);
}

long query(int a, int b, int l, int r, int k) {
if (b <= l || r <= a) {
return -1L;
}
if (a <= l && r <= b) {
return Vs[k];
} else  {
long vl = query(a, b, l, (l + r) / 2, 2 * k + 1);
long vr = query(a, b, (l + r) / 2, r, 2 * k + 2);
return merge(vl, vr);
}
}
}

class HLDecomposition {
int n;
int[] depth;
int[] heavy;
int[] parent;
int[] sz;
ArrayList<Integer>[] g;
int[] id;

@SuppressWarnings("unchecked")
public HLDecomposition(int n) {
this.n = n;
depth = new int[n];
heavy = new int[n];
parent = new int[n];
id = new int[n];
sz = new int[n];
g = new ArrayList[n];
for (int i = 0; i < n; ++i) {
g[i] = new ArrayList<>();
}
Arrays.fill(id, -1);
Arrays.fill(parent, -1);
Arrays.fill(heavy, -1);
}

void ae(int a, int b) {
}

void pre() {
dfs(0, -1);
bfs();
}

void bfs() {
ArrayDeque<Integer> pend = new ArrayDeque<>();
int gen = 0;
while (!pend.isEmpty()) {
int v = pend.pollFirst();
int top = v;
for (; v != -1; v = heavy[v]) {
id[v] = gen++;
for (int d : g[v]) {
if (d == parent[v] || d == heavy[v]) {
continue;
}
}
}
}
}

int lca(int u, int v) {
int tmp = u;
u = v;
v = tmp;
}
} else  {
if (depth[u] > depth[v]) {
int tmp = u;
u = v;
v = tmp;
}
return u;
}
}

int dfs(int c, int p) {
parent[c] = p;
int s = 1;
for (int d : g[c]) {
if (d == p)
continue;
depth[d] = depth[c] + 1;
s += dfs(d, c);
}
sz[c] = s;
for (int d : g[c])
if (sz[d] * 2 >= sz[c]) {
heavy[c] = d;
}
return s;
}

}