kuangbin模板题，看起来十分高大上
/* ***********************************************
Author :kuangbin
Created Time :2013-9-4 0:13:15
File Name :HDU4010.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
//动态维护一组森林，要求支持一下操作:
//link(a,b) : 如果a,b不在同一颗子树中，则通过在a,b之间连边的方式，连接这两颗子树
//cut(a,b) : 如果a,b在同一颗子树中，且a!=b,则将a视为这颗子树的根以后，切断b与其父亲结点的连接
//ADD(a,b,w): 如果a,b在同一颗子树中，则将a,b之间路径上所有点的点权增加w
//query(a,b): 如果a,b在同一颗子树中，返回a,b之间路径上点权的最大值
const int MAXN = ;
int ch[MAXN][],pre[MAXN],key[MAXN];
int add[MAXN],rev[MAXN],Max[MAXN];
bool rt[MAXN]; void Update_Add(int r,int d)
{
if(!r)return;
key[r] += d;
add[r] += d;
Max[r] += d;
}
void Update_Rev(int r)
{
if(!r)return;
swap(ch[r][],ch[r][]);
rev[r] ^= ;
}
void push_down(int r)
{
if(add[r])
{
Update_Add(ch[r][],add[r]);
Update_Add(ch[r][],add[r]);
add[r] = ;
}
if(rev[r])
{
Update_Rev(ch[r][]);
Update_Rev(ch[r][]);
rev[r] = ;
}
}
void push_up(int r)
{
Max[r] = max(max(Max[ch[r][]],Max[ch[r][]]),key[r]);
}
void Rotate(int x)
{
int y = pre[x], kind = ch[y][]==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]][]==y] = x;
push_up(y);
}
//P函数先将根结点到r的路径上所有的结点的标记逐级下放
void P(int r)
{
if(!rt[r])P(pre[r]);
push_down(r);
}
void Splay(int r)
{
P(r);
while( !rt[r] )
{
int f = pre[r], ff = pre[f];
if(rt[f])
Rotate(r);
else if( (ch[ff][]==f)==(ch[f][]==r) )
Rotate(f), Rotate(r);
else
Rotate(r), Rotate(r);
}
push_up(r);
}
int Access(int x)
{
int y = ;
for( ; x ; x = pre[y=x])
{
Splay(x);
rt[ch[x][]] = true, rt[ch[x][]=y] = false;
push_up(x);
}
return y;
}
//判断是否是同根(真实的树，非splay)
bool judge(int u,int v)
{
while(pre[u]) u = pre[u];
while(pre[v]) v = pre[v];
return u == v;
}
//使r成为它所在的树的根
void mroot(int r)
{
Access(r);
Splay(r);
Update_Rev(r);
}
//调用后u是原来u和v的lca,v和ch[u][1]分别存着lca的2个儿子
//(原来u和v所在的2颗子树)
void lca(int &u,int &v)
{
Access(v), v = ;
while(u)
{
Splay(u);
if(!pre[u])return;
rt[ch[u][]] = true;
rt[ch[u][]=v] = false;
push_up(u);
u = pre[v = u];
}
}
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[ch[v][]] = pre[v];
pre[v] = ;
rt[ch[v][]] = true;
ch[v][] = ;
push_up(v);
}
void ADD(int u,int v,int w)
{
if(!judge(u,v))
{
puts("-1");
return;
}
lca(u,v);
Update_Add(ch[u][],w);
Update_Add(v,w);
key[u] += w;
push_up(u);
}
void query(int u,int v)
{
if(!judge(u,v))
{
puts("-1");
return;
}
lca(u,v);
printf("%d\n",max(max(Max[v],Max[ch[u][]]),key[u]));
} struct Edge
{
int to,next;
}edge[MAXN*];
int head[MAXN],tot;
void addedge(int u,int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u)
{
for(int i = head[u];i != -; i = edge[i].next)
{
int v = edge[i].to;
if(pre[v] != )continue;
pre[v] = u;
dfs(v);
}
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,q,u,v;
while(scanf("%d",&n) == )
{
tot = ;
for(int i = ;i <= n;i++)
{
head[i] = -;
pre[i] = ;
ch[i][] = ch[i][] = ;
rev[i] = ;
add[i] = ;
rt[i] = true;
}
Max[] = -;
for(int i = ;i < n;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
for(int i = ;i <= n;i++)
{
scanf("%d",&key[i]);
Max[i] = key[i];
}
scanf("%d",&q);
pre[] = -;
dfs();
pre[] = ;
int op;
while(q--)
{
scanf("%d",&op);
if(op == )
{
int x,y;
scanf("%d%d",&x,&y);
link(x,y);
}
else if(op == )
{
int x,y;
scanf("%d%d",&x,&y);
cut(x,y);
}
else if(op == )
{
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 ;
}