Snacks

  1 #include<cstdio>  2 #include<vector>  3 #include<iostream>  4 #include<cstring>  5 #pragma comment(linker, "/STACK:1024000000,1024000000")  6 #define LL long long  7 #define N 100100  8 #define lson (x<<1)  9 #define rson (x<<1|1) 10 #define mid ((l+r)>>1) 11 using namespace std; 12 struct node{ 13     LL sum,lazy; 14 }a[N<<2]; 15 LL val[N]; 16 int L[N],R[N]; 17 LL spre[N]; 18 int index; 19 bool vis[N]; 20 vector<int>e[N]; 21 void init(){ 22     //for(int i=0;i<N;++i)e[i].clear(); 23     //memset(a,0,sizeof(a)); 24     memset(vis,0,sizeof(vis)); 25     memset(L,0,sizeof(L)); 26     memset(R,0,sizeof(R)); 27     memset(val,0,sizeof(val)); 28     memset(spre,0,sizeof(spre)); 29     index=0; 30 } 31 void dfs(int num,LL v){ 32     vis[num]=1; 33     ++index; 34     L[num]=index; 35     for(LL i=0;i<e[num].size();i++) 36         if(!vis[e[num][i]])dfs(e[num][i],v+val[e[num][i]]); 37     e[num].clear(); 38     spre[L[num]]=v; 39     R[num]=index; 40 } 41 void push_up(int x){ 42     a[x].sum=max(a[lson].sum,a[rson].sum); 43 } 44 void push_down(int x){ 45     a[rson].sum+=a[x].lazy; 46     a[rson].lazy+=a[x].lazy; 47     a[lson].sum+=a[x].lazy; 48     a[lson].lazy+=a[x].lazy; 49     a[x].lazy=0; 50 } 51 void build(int x,int l,int r){ 52     a[x].lazy=a[x].sum=0; 53     if(l==r){ 54         a[x].sum=spre[l]; 55         return; 56     } 57     build(lson,l,mid); 58     build(rson,mid+1,r); 59     push_up(x); 60 } 61 void add(int x,int l,int r,int cl,int cr,LL v){ 62     if(cl<=l&&r<=cr){ 63         a[x].sum+=v; 64         a[x].lazy+=v; 65         return; 66     } 67     if(a[x].lazy!=0)push_down(x);/**except this!!!**/ 68     if(cl<=mid)add(lson,l,mid,cl,cr,v); 69     if(mid<cr)add(rson,mid+1,r,cl,cr,v); 70     push_up(x); 71 } 72 LL query(int x,int l,int r,int ql,int qr){ 73     if(ql<=l&&r<=qr)return a[x].sum; 74     if(a[x].lazy!=0)push_down(x); 75     LL temp=-(LL)1000000000000000000; 76     if(ql<=mid)temp=max(temp,query(lson,l,mid,ql,qr)); 77     if(mid<qr)temp=max(temp,query(rson,mid+1,r,ql,qr)); 78     return temp; 79 } 80 int main(void){ 81     int T,n,m; 82     scanf("%d",&T); 83     for(int i=1;i<=T;++i){ 84       /*if(i==10)while(1); 85         WA when i==10*/ 86         init(); 87         scanf("%d%d",&n,&m); 88         for(int j=1;j<n;++j){ 89             int x,y; 90             scanf("%d%d",&x,&y);x++,y++; 91             e[x].push_back(y); 92             e[y].push_back(x); 93         } 94         for(int j=1;j<=n;++j) 95             scanf("%I64d",&val[j]); 96         dfs(1,val[1]); 97         build(1,1,n); 98         printf("Case #%d:\n",i); 99         while(m--){100             int type;101             scanf("%d",&type);102             if(type==0){103                 int x,v;104                 scanf("%d%d",&x,&v);x++;105                 LL diff=(LL)v-val[x];106                 val[x]=(LL)v;107                 add(1,1,n,L[x],R[x],diff);108             }else if(type==1){109                 int x;110                 scanf("%d",&x);x++;111                 LL temp=query(1,1,n,L[x],R[x]);112                 printf("%I64d\n",temp);113             }114         }115     }116     return 0;117 }