Snacks

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

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

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

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

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

接下来n−1n−1行，每行两个整数xx和y0≤x,y<n)y0≤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 commentlinker, “/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 commentlinker, "/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;
    memsethead,-1,sizeofhead));
}
void addedgeint u,int v)
{
    E[cnt].v = v;
    E[cnt].next = head[u];
    head[u] = cnt++;
}
void dfsint u,int pre)
{
    b[u] = index++;
    range[u] = index - 1;
    forint i = head[u];i!=-1;i = E[i].next)
    {
        ifE[i].v==pre) continue;
        dfsE[i].v,u);
    }
    e[u] = index;
}
void pushdownLL x)
{
    ifT[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 pushupLL x)
{
    T[x].max = maxT[x*2].max,T[x*2+1].max);
}
void buildLL x,LL l,LL r)
{
    T[x].l = l ,T[x].r = r,T[x].laz = 0, T[x].max = 0;
    ifl==r) return;
    LL mid = l + r)/2;
    buildx*2,l,mid);
    buildx*2+1,mid+1,r);
    pushupx);
}
void updateLL x,LL l,LL r,LL val)
{
    ifT[x].l == l && T[x].r == r)
    {
        T[x].max += val;
        T[x].laz += val;
        return ;
    }
    pushdownx);
    LL mid = T[x].l + T[x].r)/2;
    ifr<=mid)
        updatex*2,l,r,val);
    else ifl>mid)
        updatex*2+1,l,r,val);
    else
    {
        updatex*2,l,mid,val);
        updatex*2+1,mid+1,r,val);
    }
    pushupx);
}
LL queryLL x, LL l, LL r)
{
    ifT[x].l == l && T[x].r == r)
    {
        return T[x].max;
    }
    pushdownx);
    LL mid =  T[x].l + T[x].r)/2;
    ifr<=mid)
        return queryx*2,l,r);
    else ifl>mid)
        return queryx*2+1,l,r);
    else 
        return maxqueryx*2,l,mid),queryx*2+1,mid+1,r));
    
}
int main)
{
    int cas = 1;
    LL tt;
    scanf"%lld",&tt);
    whilett--)
    {
        init);
        LL op,f,t;
        scanf"%lld%lld",&n,&m);
        forLL i= 0;i<n - 1;i++)
        {
            scanf"%lld%lld",&f,&t);
            addedgef,t);
            addedget,f);
        }
        dfs0,-1);
        forint i = 0;i<n;i++)
            scanf"%lld",&val[i]);
        build1,0,n-1);
        forint i= 0;i<n;i++)
            update1,b[i],e[i]-1,val[i]);
        printf"Case #%d:
",cas++);
        whilem--)
        {
            scanf"%lld",&op);
            ifop==0)
            {
                scanf"%lld%lld",&f,&t);//把f点的价值修改为t
                update1,b[f],e[f]-1,t-val[f]);
                val[f] = t;
            }
            else ifop==1)
            {
                scanf"%lld",&f);//查询x点子树最大值
                printf"%lld
",query1,b[f],e[f]-1));
            }
        }
    }
}