树链剖分 JAG Summer 2012 Day 4 D Do use segment tree

#include 
using namespace std;
typedef long long LL;

#define lson o v = v;
	edges->next = H[u];
	H[u] = edges++;
}

void pushup(int o)
{
	tree[o].sum = tree[ls].sum + tree[rs].sum;
	tree[o].tmax = max(tree[ls].tmax, tree[rs].tmax);
	tree[o].tmax = max(tree[o].tmax, tree[ls].rmax + tree[rs].lmax);
	
	tree[o].lmax = max(tree[ls].lmax, tree[ls].sum + tree[rs].lmax);
	tree[o].rmax = max(tree[rs].rmax, tree[rs].sum + tree[ls].rmax);
}

void pushdown(int o, int L, int R)
{
	if(tree[o].lazy != INF) {
		int mid = (L + R) >> 1, t;
		t = tree[o].lazy * (mid - L + 1);
		tree[ls] = node(max(tree[o].lazy, t), max(tree[o].lazy, t), max(tree[o].lazy, t), t, tree[o].lazy);
		
		t = tree[o].lazy * (R - mid);
		tree[rs] = node(max(tree[o].lazy, t), max(tree[o].lazy, t), max(tree[o].lazy, t), t, tree[o].lazy);
		tree[o].lazy = INF;
	}
}

node merge(node a, node b)
{
	node ans;
	ans.sum = a.sum + b.sum;
	ans.tmax = max(a.tmax, b.tmax);
	ans.tmax = max(ans.tmax, a.rmax + b.lmax);
	
	ans.lmax = max(a.lmax, a.sum + b.lmax);
	ans.rmax = max(b.rmax, b.sum + a.rmax);
	return ans;
}

void build(int o, int L, int R)
{
	tree[o] = node(0, 0, 0, 0, INF);
	if(L == R) {
		tree[o] = node(a[mpp[L]], a[mpp[L]], a[mpp[L]], a[mpp[L]], INF);
		return;
	}
	int mid = (L + R) >> 1;
	build(lson);
	build(rson);
	pushup(o);
}

void update(int o, int L, int R, int ql, int qr, int val)
{
	if(ql = R) {
		int t = (R - L + 1) * val;
		tree[o] = node(max(val, t), max(val, t), max(val, t), t, val);
		return;
	}
	pushdown(o, L, R);
	int mid = (L + R) >> 1;
	if(ql  mid) update(rson, ql, qr, val);
	pushup(o);
}

node query(int o, int L, int R, int ql, int qr)
{
	if(ql = R) return tree[o];
	pushdown(o, L, R);
	int mid = (L + R) >> 1;
	node ans;
	if(ql > mid) ans = query(rson, ql, qr);
	else if(qr next) {
		if(e->v != fa[u]) {
			dep[e->v] = dep[u] + 1;
			fa[e->v] = u;
			dfs1(e->v);
			size[u] += size[e->v];
			if(size[son[u]] v]) son[u] = e->v;
		}
	}
}

void dfs2(int u, int tp)
{
	w[u] = ++z, top[u] = tp;
	if(son[u]) dfs2(son[u], tp);
	for(Edge *e = H[u]; e; e = e->next) {
		if(e->v != fa[u] && e->v != son[u]) dfs2(e->v, e->v);
	}
}

void solve1(int a, int b, int c)
{
	int f1 = top[a], f2 = top[b];
	while(f1 != f2) {
		if(dep[f1]  dep[b]) swap(a, b);
	update(1, 1, n, w[a], w[b], c);
}

void solve2(int a, int b)
{
	int f1 = top[a], f2 = top[b];
	node ans1, ans2;
	int flag1 = 0, flag2 = 0;
	while(f1 != f2) {
		if(dep[f1] > dep[f2]) {
			if(flag1 == 0) flag1 = 1, ans1 = query(1, 1, n, w[f1], w[a]);
			else ans1 = merge(query(1, 1, n, w[f1], w[a]), ans1);
			a = fa[f1], f1 = top[a];
		}
		else {
			if(flag2 == 0) flag2 = 1, ans2 = query(1, 1, n, w[f2], w[b]);
			else ans2 = merge(query(1, 1, n, w[f2], w[b]), ans2);
			b = fa[f2], f2 = top[b];
		}
	}
	if(dep[a] > dep[b]) {
		if(flag1 == 0) flag1 = 1, ans1 = query(1, 1, n, w[b], w[a]);
		else ans1 = merge(query(1, 1, n, w[b], w[a]), ans1);
	}
	else {
		if(flag2 == 0) flag2 = 1, ans2 = query(1, 1, n, w[a], w[b]);
		else ans2 = merge(query(1, 1, n, w[a], w[b]), ans2);
	}
	
	int res = 0;
	if(flag1 == 0 && flag2 == 1) {
		res = ans2.tmax;
	}
	else if(flag1 == 1 && flag2 == 0) {
		res = ans1.tmax;
	}
	else {
		res = max(ans1.tmax, ans2.tmax);
		res = max(res, ans1.lmax + ans2.lmax);
	}
	printf("%dn", res);
}


void work()
{
	for(int i = 1; i