Snacks

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5692

dfs序+线段树

这道题涉及到对整棵树的值修改，考虑将树状结构用dfs序转化成线性结构，将树的修改转化为区间修改以降低时间复杂度（之前组队赛的时候遇到一道类似的没调出来...代码能力太缺乏了...）

代码如下：

 #include<cstdio>

 #include<vector>

 #include<iostream>

 #include<cstring>

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

 #define LL long long

 #define N 100100

 #define lson (x<<1)

 #define rson (x<<1|1)

 #define mid ((l+r)>>1)

 using namespace std;

 struct node{

     LL sum,lazy;

 }a[N<<];

 LL val[N];

 int L[N],R[N];

 LL spre[N];

 int index;

 bool vis[N];

 vector<int>e[N];

 void init(){

     //for(int i=0;i<N;++i)e[i].clear();

     //memset(a,0,sizeof(a));

     memset(vis,,sizeof(vis));

     memset(L,,sizeof(L));

     memset(R,,sizeof(R));

     memset(val,,sizeof(val));

     memset(spre,,sizeof(spre));

     index=;

 }

 void dfs(int num,LL v){

     vis[num]=;

     ++index;

     L[num]=index;

     for(LL i=;i<e[num].size();i++)

         if(!vis[e[num][i]])dfs(e[num][i],v+val[e[num][i]]);

     e[num].clear();

     spre[L[num]]=v;

     R[num]=index;

 }

 void push_up(int x){

     a[x].sum=max(a[lson].sum,a[rson].sum);

 }

 void push_down(int x){

     a[rson].sum+=a[x].lazy;

     a[rson].lazy+=a[x].lazy;

     a[lson].sum+=a[x].lazy;

     a[lson].lazy+=a[x].lazy;

     a[x].lazy=;

 }

 void build(int x,int l,int r){

     a[x].lazy=a[x].sum=;

     if(l==r){

         a[x].sum=spre[l];

         return;

     }

     build(lson,l,mid);

     build(rson,mid+,r);

     push_up(x);

 }

 void add(int x,int l,int r,int cl,int cr,LL v){

     if(cl<=l&&r<=cr){

         a[x].sum+=v;

         a[x].lazy+=v;

         return;

     }

     if(a[x].lazy!=)push_down(x);/**except this!!!**/

     if(cl<=mid)add(lson,l,mid,cl,cr,v);

     if(mid<cr)add(rson,mid+,r,cl,cr,v);

     push_up(x);

 }

 LL query(int x,int l,int r,int ql,int qr){

     if(ql<=l&&r<=qr)return a[x].sum;

     if(a[x].lazy!=)push_down(x);

     LL temp=-(LL);

     if(ql<=mid)temp=max(temp,query(lson,l,mid,ql,qr));

     if(mid<qr)temp=max(temp,query(rson,mid+,r,ql,qr));

     return temp;

 }

 int main(void){

     int T,n,m;

     scanf("%d",&T);

     for(int i=;i<=T;++i){

       /*if(i==10)while(1);

         WA when i==10*/

         init();

         scanf("%d%d",&n,&m);

         for(int j=;j<n;++j){

             int x,y;

             scanf("%d%d",&x,&y);x++,y++;

             e[x].push_back(y);

             e[y].push_back(x);

         }

         for(int j=;j<=n;++j)

             scanf("%I64d",&val[j]);

         dfs(,val[]);

         build(,,n);

         printf("Case #%d:\n",i);

         while(m--){

             int type;

             scanf("%d",&type);

             if(type==){

                 int x,v;

                 scanf("%d%d",&x,&v);x++;

                 LL diff=(LL)v-val[x];

                 val[x]=(LL)v;

                 add(,,n,L[x],R[x],diff);

             }else if(type==){

                 int x;

                 scanf("%d",&x);x++;

                 LL temp=query(,,n,L[x],R[x]);

                 printf("%I64d\n",temp);

             }

         }

     }

     return ;

 }