题意:

感谢@JCarlson的翻译

给你一个树,点上有权值

你需要....

1,连接x,y这一条边(如果非法输出个-1,成功啥都别输出好了)

2,以x为根,断y和y的父亲(如果非法输出个-1,成功也啥都别输了)

3,x到y的路径上权值+w(非法输出-1,成功不管)

4,询问x到y路径上权值的最大值(非法输出-1,成功输出最大值)

所以呢...直接LCT

第一次写LCT带权值的,稍微调试了下...

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    bool rev;
    int weight;
    int max_weight;
    int tag;
    node * ch[2];
    node * father;
};
node * null;
node * a[300005];
node * new_node()
{
    static node a[300005];
    static int top=0;
    return &a[top++];
}
void push_down(node * x)
{
    if (x->rev)
    {
        swap(x->ch[0],x->ch[1]);
        x->ch[0]->rev^=1;
        x->ch[1]->rev^=1;
        x->rev=0;
    }
    if (x->tag)
    {
        if (x->ch[0]!=null)
        {
            x->ch[0]->tag+=x->tag;
            x->ch[0]->weight+=x->tag;
            x->ch[0]->max_weight+=x->tag;
        }
        if (x->ch[1]!=null)
        {
            x->ch[1]->tag+=x->tag;
            x->ch[1]->weight+=x->tag;
            x->ch[1]->max_weight+=x->tag;
        }
        x->tag=0;
    }
}
void update(node * x)
{
    x->max_weight=max(x->ch[0]->max_weight,x->ch[1]->max_weight);
    x->max_weight=max(x->weight,x->max_weight);
}
void clear(node * x)
{
    x->rev=false;
    x->tag=0;
    x->weight=0;
    x->max_weight=0;
    x->ch[0]=null;
    x->ch[1]=null;
    x->father=null;
}
int get_up(node * x)
{
    if (x->father->ch[0]==x) return 0;
    if (x->father->ch[1]==x) return 1;
    return -1;
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]->father=x;
    y->ch[!c]=x;
    y->max_weight=x->max_weight;
    y->father=x->father;
    update(x);
    x->father=y;
    x=y;
}
void splay(node * x)
{
    for (;;)
    {
        push_down(x->father->father);
        push_down(x->father);
        push_down(x);
        int t1=get_up(x);
        if (t1==-1) return;
        int t2=get_up(x->father);
        if (t2==-1)
        {
            x=x->father;
            rotate(x,t1);
            return;
        }
        int t3=get_up(x->father->father);
        if (t3==-1)
        {
            x=x->father;
            x=x->father;
            if (t1==t2)
            {
                rotate(x,t2);
                rotate(x,t1);
            }
            else
            {
                rotate(x->ch[t2],t1);
                rotate(x,t2);
            }
        }
        else
        {
            x=x->father;
            x=x->father;
            if (t1==t2)
            {
                x=x->father;
                rotate(x->ch[t3],t2);
                rotate(x->ch[t3],t1);
            }
            else
            {
                rotate(x->ch[t2],t1);
                x=x->father;
                rotate(x->ch[t3],t2);
            }
            x=x->ch[t3];
        }
    }
}
void access(node * x)
{
    for (;;)
    {
        splay(x);
        if (x->father==null)
        {
            x->ch[1]=null;
            update(x);
            return;
        }
        splay(x->father);
        x->father->ch[1]=x;
        update(x->father);
    }
}
void evert(node * x)
{
    access(x);
    x->rev=true;
}
void link(node * x,node * y)
{
    evert(x);
    x->father=y;
}
void cut(node * x,node * y)
{
    evert(x);
    access(y);
    y->ch[0]->father=null;
    y->ch[0]=null;
    update(y);
}
node * findroot(node * x)
{
    access(x);
    node * t=x;
    for (;;)
    {
        push_down(t);
        if (t->ch[0]==null) return t;
        t=t->ch[0];
    }
}
int query(node * x,node * y)
{
    evert(x);
    access(y);
    return max(y->ch[0]->max_weight,y->weight);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    int i;
    null=new_node();
    clear(null);
    for (i=0;i<300000;i++)
    {
        a[i]=new_node();
    }
    for (;scanf("%d",&n)!=-1;)
    {
        int i;
        for (i=0;i<n;i++)
        {
            clear(a[i]);
        }
        static int x[300005],y[300005];
        for (i=1;i<n;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            x[i]--;
            y[i]--;
        }
        for (i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            a[i]->weight=x;
            a[i]->max_weight=x;
        }
        for (i=1;i<n;i++)
        {
            link(a[x[i]],a[y[i]]);
        }
        int m;
        scanf("%d",&m);
        for (i=0;i<m;i++)
        {
            int oper;
            scanf("%d",&oper);
            int x,y;
            if (oper==1)
            {
                scanf("%d%d",&x,&y);
                x--;
                y--;
                if (findroot(a[x])!=findroot(a[y]))
                {
                    link(a[x],a[y]);
                }
                else
                {
                    printf("-1\n");
                }
            }
            else if (oper==2)
            {
                scanf("%d%d",&x,&y);
                x--;
                y--;
                if ((x!=y)&&(findroot(a[x])==findroot(a[y])))
                {
                    cut(a[x],a[y]);
                }
                else
                {
                    printf("-1\n");
                }
            }
            else if (oper==3)
            {
                int w;
                scanf("%d%d%d",&w,&x,&y);
                x--;
                y--;
                if (findroot(a[x])==findroot(a[y]))
                {
                    evert(a[x]);
                    access(a[y]);
                    a[y]->weight+=w;
                    a[y]->ch[0]->tag+=w;
                    a[y]->ch[0]->weight+=w;
                    a[y]->ch[0]->max_weight+=w;
                    update(a[y]);
                }
                else
                {
                    printf("-1\n");
                }
            }
            else
            {
                scanf("%d%d",&x,&y);
                x--;
                y--;
                if (findroot(a[x])==findroot(a[y]))
                {
                    printf("%d\n",query(a[x],a[y]));
                }
                else
                {
                    printf("-1\n");
                }
            }
        }
        printf("\n");
    }
    return 0;
}