Snacks

百度科技园内有nn个零食机，零食机之间通过n−1n−1条路相互连通。每个零食机都有一个值vv，表示为小度熊提供零食的价值。 

由于零食被频繁的消耗和补充，零食机的价值vv会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。 

为小度熊规划一个路线，使得路线上的价值总和最大。 

Input输入数据第一行是一个整数T(T≤10)T(T≤10)，表示有TT组测试数据。 

对于每组数据，包含两个整数n,m(1≤n,m≤100000)n,m(1≤n,m≤100000)，表示有nn个零食机，mm次操作。 

接下来n−1n−1行，每行两个整数xx和y(0≤x,y<n)y(0≤x,y<n)，表示编号为xx的零食机与编号为yy的零食机相连。 

接下来一行由nn个数组成，表示从编号为0到编号为n−1n−1的零食机的初始价值v(|v|<100000)v(|v|<100000)。 

接下来mm行，有两种操作：0 x y0 x y，表示编号为xx的零食机的价值变为yy；1 x1 x，表示询问从编号为0的零食机出发，必须经过编号为xx零食机的路线中，价值总和的最大值。 

本题可能栈溢出，辛苦同学们提交语言选择c++，并在代码的第一行加上： 

`#pragma comment(linker, “/STACK:1024000000,1024000000”) `Output对于每组数据，首先输出一行”Case #?:”，在问号处应填入当前数据的组数，组数从1开始计算。 

对于每次询问，输出从编号为0的零食机出发，必须经过编号为xx零食机的路线中，价值总和的最大值。 
Sample Input

1
6 5
0 1
1 2
0 3
3 4
5 3
7 -5 100 20 -5 -7
1 1
1 3
0 2 -1
1 1
1 5

Sample Output

Case #1:
102
27
2
20

利用DFS序可以将对子树的操作转化为对区间的操作，线段树

#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
typedef long long LL;
const int MAXN = 100002;
//一开始全部Insert一遍然后再操作
struct node
{
    LL l,r;
    LL max;//子树中最大的节点
    LL laz;
}T[MAXN*4+9];
struct edge
{
    LL v,next;
}E[MAXN];
LL head[MAXN], cnt, index;
LL b[MAXN],e[MAXN], val[MAXN];
LL range[MAXN];
LL n, m;
void init()
{
    index = cnt = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    E[cnt].v = v;
    E[cnt].next = head[u];
    head[u] = cnt++;
}
void dfs(int u,int pre)
{
    b[u] = index++;
    range[u] = index - 1;
    for(int i = head[u];i!=-1;i = E[i].next)
    {
        if(E[i].v==pre) continue;
        dfs(E[i].v,u);
    }
    e[u] = index;
}
void pushdown(LL x)
{
    if(T[x].laz)
    {
        T[x*2].laz += T[x].laz;
        T[x*2+1].laz += T[x].laz;
        T[x*2].max += T[x].laz;
        T[x*2+1].max += T[x].laz;
        T[x].laz = 0;
    }
}
void pushup(LL x)
{
    T[x].max = max(T[x*2].max,T[x*2+1].max);
}
void build(LL x,LL l,LL r)
{
    T[x].l = l ,T[x].r = r,T[x].laz = 0, T[x].max = 0;
    if(l==r) return;
    LL mid = (l + r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);
}
void update(LL x,LL l,LL r,LL val)
{
    if(T[x].l == l && T[x].r == r)
    {
        T[x].max += val;
        T[x].laz += val;
        return ;
    }
    pushdown(x);
    LL mid = (T[x].l + T[x].r)/2;
    if(r<=mid)
        update(x*2,l,r,val);
    else if(l>mid)
        update(x*2+1,l,r,val);
    else
    {
        update(x*2,l,mid,val);
        update(x*2+1,mid+1,r,val);
    }
    pushup(x);
}
LL query(LL x, LL l, LL r)
{
    if(T[x].l == l && T[x].r == r)
    {
        return T[x].max;
    }
    pushdown(x);
    LL mid = ( T[x].l + T[x].r)/2;
    if(r<=mid)
        return query(x*2,l,r);
    else if(l>mid)
        return query(x*2+1,l,r);
    else 
        return max(query(x*2,l,mid),query(x*2+1,mid+1,r));
    
}
int main()
{
    int cas = 1;
    LL tt;
    scanf("%lld",&tt);
    while(tt--)
    {
        init();
        LL op,f,t;
        scanf("%lld%lld",&n,&m);
        for(LL i= 0;i<n - 1;i++)
        {
            scanf("%lld%lld",&f,&t);
            addedge(f,t);
            addedge(t,f);
        }
        dfs(0,-1);
        for(int i = 0;i<n;i++)
            scanf("%lld",&val[i]);
        build(1,0,n-1);
        for(int i= 0;i<n;i++)
            update(1,b[i],e[i]-1,val[i]);
        printf("Case #%d:
",cas++);
        while(m--)
        {
            scanf("%lld",&op);
            if(op==0)
            {
                scanf("%lld%lld",&f,&t);//把f点的价值修改为t
                update(1,b[f],e[f]-1,t-val[f]);
                val[f] = t;
            }
            else if(op==1)
            {
                scanf("%lld",&f);//查询x点子树最大值
                printf("%lld
",query(1,b[f],e[f]-1));
            }
        }
    }
}