Heavy Light Decomposition Untested

heavylightuntested.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;
const int N = 100005;

int n, h[N], w[N], p[N], tree[N], ch[N], pos[N], head[N], val[N], chain, id;
vector<int> adj[N];

void dfsHeavy(int u) {
	w[u] = 1;
	for (int i = 0; i < adj[u].size(); ++i) {
		int v = adj[u][i];
		if (v != p[u]) {
			p[v] = u;
			dfs(v);
			w[u] += w[v];
			if (w[h[u]] < w[v])
				h[u] = v;
		}
	}
}

void dfsLight(int u) {
	if (!head[chain]) head[chain] = u;
	ch[u] = chain;
	pos[u] = id;
	node[id] = u;
	arr[id++] = val[u];
	if (h[u]) dfsLight(h[u]);
	for (int i = 0; i < adj[u].size(); ++i) {
		int v = adj[u][i];
		if (v != p[u] && v != h[u]) {
			chain++;
			dfsLight(v);
		}
	}
}

void heavy_light(int n) {
	dfsLight(n);
	dfsHeavy(n);
	// O(1) segment
	for (int i = 0; i < n; +i)
		st[0][i] = arr[i];
	for (int j = 0; (2 << j) <= n; ++j) {
		for (int i = 0; i + (2 << j) <= n; ++i) {
			int k = i + (1 << j);
			st[j + 1][i] = min(st[j][i], st[j][k]);
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		int a, b; scanf("%d%d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int root = rand() % n;
	heavy_light(root);
}