【题意】给出一棵树，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;
}
