程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4010 Query on The Trees

HDU 4010 Query on The Trees

編輯：C++入門知識

HDU 4010 Query on The Trees

題意：

一棵樹支持合並、分離、路徑加權值、路徑權值最大值

思路：

LCT入門題也是我的第一道… 代碼來源於kuangbin巨巨我只是整理出自己的風格留作模版…

LCT比較好的入門資料是——《QTREE解法的一些研究》

LCT基本做法就是先dfs建樹然後根據輸入做上述4個操作

對於合並就是把u轉到樹根然後接在v上

對於分離就是把u轉到splay的根然後切斷與左子樹的連接

對於路徑加值就是求出lca 然後包含u和v的子樹以及lca點進行加值

對於路徑求最值就是求出lca 然後和上面一樣分三部分進行

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define N  300010
#define L(x) (ch[x][0])
#define R(x) (ch[x][1])

struct Edge {
	int v, next;
} ed[N * 2];
int head[N], tot;
int ch[N][2], pre[N], key[N], add[N], rev[N], Max[N];
bool rt[N];

void Update_Add(int u, int d) {
	if (!u)
		return;
	key[u] += d;
	add[u] += d;
	Max[u] += d;
}

void Update_Rev(int u) {
	if (!u)
		return;
	swap(L(u), R(u));
	rev[u] ^= 1;
}

void down(int u) {
	if (add[u]) {
		Update_Add(L(u), add[u]);
		Update_Add(R(u), add[u]);
		add[u] = 0;
	}
	if (rev[u]) {
		Update_Rev(L(u));
		Update_Rev(R(u));
		rev[u] = 0;
	}
}

void up(int u) {
	Max[u] = max(max(Max[L(u)], Max[R(u)]), key[u]);
}

//Rotate P Splay 一般不變
void Rotate(int x) {
	int y = pre[x], kind = ch[y][1] == x;
	ch[y][kind] = ch[x][!kind];
	pre[ch[y][kind]] = y;
	pre[x] = pre[y];
	pre[y] = x;
	ch[x][!kind] = y;
	if (rt[y])
		rt[y] = false, rt[x] = true;
	else
		ch[pre[x]][ch[pre[x]][1] == y] = x;
	up(y);
}

//P函數先將splay根結點到u的路徑上所有的結點的標記逐級下放
void P(int u) {
	if (!rt[u])
		P(pre[u]);
	down(u);
}

void Splay(int u) {
	P(u);
	while (!rt[u]) {
		int fa = pre[u], ffa = pre[fa];
		if (rt[fa])
			Rotate(u);
		else if ((R(ffa) == fa) == (R(fa) == u))
			Rotate(fa), Rotate(u);
		else
			Rotate(u), Rotate(u);
	}
	up(u);
}

//將root到u的路徑變成實邊
int Access(int u) {
	int v = 0;
	for (; u; u = pre[v = u]) {
		Splay(u);
		rt[R(u)] = true, rt[R(u) = v] = false;
		up(u);
	}
	return v;
}

//判斷是否是同樹(真實的樹，非splay)
bool judge(int u, int v) {
	while (pre[u])
		u = pre[u];
	while (pre[v])
		v = pre[v];
	return u == v;
}

//使u成為它所在的樹的根
void mroot(int u) {
	Access(u);
	Splay(u);
	Update_Rev(u);
}

//調用後u是原來u和v的lca,v和ch[u][1]分別存著lca的2個兒子(原來u和v所在的2顆子樹)
void lca(int &u, int &v) {
	Access(v), v = 0;
	while (u) {
		Splay(u);
		if (!pre[u])
			return;
		rt[R(u)] = true;
		rt[R(u) = v] = false;
		up(u);
		u = pre[v = u];
	}
}

//連接兩棵樹  u接在v上
void link(int u, int v) {
	if (judge(u, v)) {
		puts("-1");
		return;
	}
	mroot(u);
	pre[u] = v;
}

//使u成為u所在樹的根，並且v和它父親的邊斷開
void cut(int u, int v) {
	if (u == v || !judge(u, v)) {
		puts("-1");
		return;
	}
	mroot(u);
	Splay(v);
	pre[L(v)] = pre[v];
	pre[v] = 0;
	rt[L(v)] = true;
	L(v) = 0;
	up(v);
}

//u-v路徑+w
void ADD(int u, int v, int w) {
	if (!judge(u, v)) {
		puts("-1");
		return;
	}
	lca(u, v);
	Update_Add(R(u), w);
	Update_Add(v, w);
	key[u] += w;
	up(u);
}

//u-v路徑最大值
void query(int u, int v) {
	if (!judge(u, v)) {
		puts("-1");
		return;
	}
	lca(u, v);
	printf("%d\n", max(max(Max[v], Max[R(u)]), key[u]));
}

void addedge(int u, int v) {
	ed[tot].v = v;
	ed[tot].next = head[u];
	head[u] = tot++;
}

//利用dfs初始化pre數組  建立LCT
void dfs(int u) {
	for (int i = head[u]; ~i; i = ed[i].next) {
		int v = ed[i].v;
		if (pre[v] != 0)
			continue;
		pre[v] = u;
		dfs(v);
	}
}

int main() {
	int n, q, u, v;
	while (scanf("%d", &n) == 1) {
		tot = 0;
		memset(head, -1, sizeof(head));
		memset(pre, 0, sizeof(pre));
		memset(ch, 0, sizeof(ch));
		memset(rev, 0, sizeof(rev));
		memset(add, 0, sizeof(add));
		for (int i = 0; i <= n; i++)
			rt[i] = true;
		Max[0] = -2000000000;
		for (int i = 1; i < n; i++) {
			scanf("%d%d", &u, &v);
			addedge(u, v);
			addedge(v, u);
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d", &key[i]);
			Max[i] = key[i];
		}
		scanf("%d", &q);
		pre[1] = -1;
		dfs(1);
		pre[1] = 0;
		int op;
		while (q--) {
			scanf("%d", &op);
			if (op == 1) {
				int x, y;
				scanf("%d%d", &x, &y);
				link(x, y);
			} else if (op == 2) {
				int x, y;
				scanf("%d%d", &x, &y);
				cut(x, y);
			} else if (op == 3) {
				int w, x, y;
				scanf("%d%d%d", &w, &x, &y);
				ADD(x, y, w);
			} else {
				int x, y;
				scanf("%d%d", &x, &y);
				query(x, y);
			}
		}
		printf("\n");
	}
	return 0;
}