HDU4010

【题意】给出一棵树，4种操作：

1）link(x,y) : 如果x(以下x都是当前节点),y不在同一颗子树中，则通过在x,y之间连边的方式，连接这两颗子树

2）cut(x,y)  : 如果x,y在同一颗子树中，且x!=y,则将x视为这颗子树的根以后，切断y与其父亲结点的连接

3）update(x,y,v): 如果x,y在同一颗子树中，则将x,y之间路径上所有点的点权增加v

4）query(x,y): 如果x,y在同一颗子树中，返回x,y之间路径上点权的最大值

【分析】花了5天终于理解动态树了，动态树分有根和无根，对应操作也不同，有根区间查询要求lca，然后区间分成x>lca,lca,lca->y三部分；而无根树是没有lca的，所以需要利用make_root()操作确定边，无根树的，cut和link操作都必须要make_root()，否则无法确定边，导致形成的不是树；而有根树根数确定的，不能make_root()随意换根，而cut，和link都的边方向都是确定的直接连(删)就可以。

还有对于没有cut和link操作的树，两种LCT都可以用，树是静态的嘛，只要维护静态区间就好了。

【AC CODE】1326ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 300000+10;
int par[MAXN],ch[MAXN][2],fa[MAXN],fz[MAXN],val[MAXN],add[MAXN],mx[MAXN];

void init()
{
	clc(par,0);clc(ch,0);clc(fa,0);
	clc(fz,0);clc(val,0);clc(add,0);clc(mx,0);
}
inline int chd(int u){return ch[fa[u]][1] == u;}
inline void setch(int f, int u, int d){ch[f][d] = u,fa[u] = f;}
inline void push_up(int u)
{
	mx[u] = max(mx[ch[u][0]],max(mx[ch[u][1]],val[u]));
}
inline void rot(int u)
{
	int d = chd(u),y = fa[u];
	setch(fa[y],u,chd(y));
	setch(y,ch[u][d^1],d);
	setch(u,y,d^1);
	push_up(y);push_up(u);
}
inline void rev(int u)
{
	swap(ch[u][0],ch[u][1]);
	fz[u] ^= 1;
}
inline void one_add(int u, int v)
{
	if(!u) return;
	add[u] += v;
	val[u] += v;
	mx[u] += v;
}
inline void push_down(int u)
{
	if(add[u])
	{
		one_add(ch[u][0],add[u]);one_add(ch[u][1],add[u]);
		add[u] = 0;
	}
	if(fz[u])
	{
		rev(ch[u][0]),rev(ch[u][1]);
		fz[u] = 0;
	}
}
void dfs_down(int u)
{
	if(fa[u]) dfs_down(fa[u]);
	push_down(u);
}
void splay(int u)
{
	dfs_down(u);
	int rt = u;
	while(fa[rt]) rt = fa[rt];
	if(rt == u) return;
	par[u] = par[rt],par[rt] = 0;
	while(fa[u])
	{
		if(fa[fa[u]] && chd(u) == chd(fa[u])) rot(fa[u]);
		rot(u);
	}
}
void expose(int u)
{
	for(int now = u,la = 0;now;la = now,now = par[now])
	{
		splay(now);
		par[ch[now][1]] = now;fa[ch[now][1]] = par[la] = 0;
		setch(now,la,1);
		push_up(now);
	}
	splay(u);
}
int find_root(int u)
{
	expose(u);
	while(ch[u][0]) u = ch[u][0];
	return u;
}
void make_root(int u)
{
	expose(u);
	rev(u);
}
bool link(int u, int v)
{
	if(find_root(u) == find_root(v)) return false;
	make_root(u);
	par[u] = v;
	return true;
}
void cut(int u)
{
	expose(u);
	par[u] = fa[ch[u][0]] = 0;
	ch[u][0] = 0;
	push_up(u);
}
bool cut(int u, int v)
{
	if(u == v || find_root(u) != find_root(v)) return false;
	make_root(u);
	cut(v);
	return true;
}
bool update(int x, int y, int v)
{
	if(find_root(x) != find_root(y)) return false;
	make_root(x);
	expose(y);
	one_add(y,v);
	return true;
}
int query(int x, int y)
{
	if(find_root(x) != find_root(y)) return -1;
	make_root(x);
	expose(y);
	return mx[y];
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n;
	while(~scanf("%d", &n))
	{
		init();
		rep(i,1,n)
		{
			int u,v;
			scanf("%d %d", &u, &v);
			link(u,v);
		}
		repe(i,1,n)
		{
			int v;
			scanf("%d", &v);
			update(i,i,v);
		}
		int q;
		scanf("%d", &q);
		while(q--)
		{
			int op,x,y;
			scanf("%d %d %d", &op, &x, &y);
			if(1 == op)
			{
				if(!link(x,y)) puts("-1");
			}
			else if(2 == op)
			{
				if(!cut(x,y)) puts("-1");
			}
			else if(3 == op)
			{
				int z;
				scanf("%d", &z);
				if(!update(y,z,x)) puts("-1");
			}
			else printf("%d\n", query(x,y));
		}
		putchar('\n');
	}
	return 0;
}