Snacks

Time Limit:5000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Submit 

Description

百度科技园内有

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

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

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

Input

输入数据第一行是一个整数

T(T≤10)，表示有T组测试数据。 

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

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

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

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

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

`#pragma comment(linker, "/STACK:1024000000,1024000000") `

Output

对于每组数据，首先输出一行”Case #?:”，在问号处应填入当前数据的组数，组数从1开始计算。 

对于每次询问，输出从编号为0的零食机出发，必须经过编号为

x零食机的路线中，价值总和的最大值。 

Sample Input

16 50 11 20 33 45 37 -5 100 20 -5 -71 11 30 2 -11 11 5

Sample Output

Case #1:10227220 线段树＋dfs序

1 //2016.8.11  2 #pragma comment(linker, "/STACK:1024000000, 1024000000")  3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
               7 #define N 100005  8 #define lson (id<<1)  9 #define rson ((id<<1)|1) 10 #define mid ((l+r)>>1) 11  12 using namespace std; 13  14 struct node 15 { 16     long long max, lazy; 17 }tree[N*5]; 18  19 vector
             
               v[N]; 20 long long w[N], val[N];//val[i]表示从根节点走到i节点的价值和 21 int in[N], out[N], flag;//in记录查询区间的左端，out记录查询区间的右端 22  23  24 //线段树模板 25 //************************************************************************************ 26 void push_up(int id) 27 { 28     tree[id].max = max(tree[lson].max, tree[rson].max); 29     return; 30 } 31  32 void build_tree(int id, int l, int r) 33 { 34     if(l == r) 35     { 36         tree[id].max = val[l]; 37         tree[id].lazy = 0; 38         return ; 39     } 40     build_tree(lson, l, mid); 41     build_tree(rson, mid+1, r); 42     push_up(id); 43     tree[id].lazy = 0; 44     return ; 45 } 46  47 void push_down(int id, int l, int r) 48 { 49     if(tree[id].lazy) 50     { 51         tree[lson].lazy += tree[id].lazy; 52         tree[rson].lazy += tree[id].lazy; 53         tree[lson].max += tree[id].lazy; 54         tree[rson].max += tree[id].lazy; 55         tree[id].lazy = 0; 56     } 57     return ; 58 } 59  60 void ins(int id, int l, int r, int ql, int qr, int tt) 61 { 62     if(ql<=l&&r<=qr) 63     { 64         tree[id].max += tt; 65         tree[id].lazy += tt; 66         return; 67     } 68     if(tree[id].lazy) push_down(id, l, r); 69     if(ql<=mid) 70           ins(lson, l, mid, ql, qr, tt); 71     if(mid+1<=qr) 72           ins(rson, mid+1, r, ql, qr, tt); 73     push_up(id); 74     return; 75 } 76  77 long long query(int id, int l, int r, int ql, int qr) 78 { 79     if(ql<=l && r<=qr) 80     { 81         return tree[id].max; 82     } 83     if(tree[id].lazy) 84           push_down(id, l, r); 85     long long maxnum = -9999999999999; 86     if(ql<=mid) maxnum = max(maxnum, query(lson, l, mid, ql, qr)); 87     if(mid+1<=qr) maxnum = max(maxnum, query(rson, mid+1, r, ql, qr)); 88     return maxnum; 89 } 90 //************************************************************************************ 91  92 void dfs(int a, int fa, long long wight) 93 { 94     in[a] = ++flag; 95     for(int i = 0; i < v[a].size(); i++) 96     { 97         int b = v[a][i]; 98         if(b==fa)continue; 99         dfs(b, a, w[b]+wight);100     }101     out[a] = flag;102     val[in[a]] = wight;103 }104 105 int main()106 {107     int T, n, m, a, b, cmd;108     cin>>T;109     for(int kase = 1; kase <= T; kase++)110     {111         printf("Case #%d:\n", kase);112         cin>>n>>m;113         for(int i = 0; i < N; i++)114             v[i].clear();115         for(int i = 0; i < n-1; i++)116         {117             scanf("%d%d", &a, &b);118             a++; b++;119             v[a].push_back(b);120             v[b].push_back(a);121         }122         for(int i = 1 ; i <= n; i++)123           scanf("%lld", &w[i]);124         flag = 0;125         dfs(1, 0, w[1]);126         for(int i = 1; i <= n; i++)127           cout<
              
               <<" "<
               
                <