HDU 5692 (DFS序+线段树)

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <algorithm>
  5 #include <cstring>
  6 #include <vector>
  7 using namespace std;
  8 const int maxn = 1e5+5;
  9 
 10 typedef long long ll;
 11 const ll inf = 0x3f3f3f3f3f3f3f3f;
 12 int n,m;
 13 vector<int> g[maxn];
 14 ll w[maxn];
 15 int index = 1;
 16 int L[maxn],R[maxn];
 17 int vis[maxn];
 18 ll d[maxn];
 19 struct node
 20 {
 21     ll maxx;
 22     ll lazy;
 23 };
 24 node T[maxn*5];
 25 void dfs(int x,int New)
 26 {
 27     L[x] = index;
 28     for(int i=0;i<g[x].size();i++)
 29     {
 30         int v = g[x][i];
 31         if(!vis[v])
 32         {
 33             vis[v] = 1;
 34            index++;
 35            d[index] = d[New]+w[v];
 36            dfs(v,index);
 37         }
 38     }
 39     R[x] = index;
 40 }
 41 void build(int q,int l,int r)
 42 {
 43     if(l==r)
 44     {
 45         T[q].maxx = d[l];
 46         T[q].lazy = 0;
 47         return;
 48     }
 49     int mid = (l+r)/2;
 50     build(q*2,l,mid);
 51     build(q*2+1,mid+1,r);
 52     T[q].lazy = 0;
 53     T[q].maxx = max(T[q*2].maxx,T[q*2+1].maxx);
 54 }
 55 void ins(int q,int l,int r,int ql,int qr,ll tt)
 56 {
 57     if(ql<=l&&r<=qr)
 58     {
 59         T[q].maxx += tt;
 60         T[q].lazy += tt;
 61         return;
 62     }
 63     if(T[q].lazy)
 64     {
 65         T[q*2].maxx += T[q].lazy;
 66         T[q*2].lazy += T[q].lazy;
 67         T[q*2+1].maxx += T[q].lazy;
 68         T[q*2+1].lazy += T[q].lazy;
 69         T[q].lazy = 0;
 70     }
 71     int mid = (l+r)/2;
 72     if(ql<=mid) ins(q*2,l,mid,ql,qr,tt);
 73     if(mid+1<=qr) ins(q*2+1,mid+1,r,ql,qr,tt);
 74     T[q].maxx = max(T[q*2].maxx,T[q*2+1].maxx);
 75     return;
 76 }
 77 ll query(int q,int l,int r,int ql,int qr)
 78 {
 79     if(ql<=l&&qr>=r)
 80     {
 81         return T[q].maxx;
 82     }
 83     if(T[q].lazy)
 84     {
 85         T[q*2].maxx += T[q].lazy;
 86         T[q*2].lazy += T[q].lazy;
 87         T[q*2+1].maxx += T[q].lazy;
 88         T[q*2+1].lazy += T[q].lazy;
 89         T[q].lazy = 0;
 90     }
 91     ll maxx = -inf;   //坑点
 92     int mid = (l+r)/2;
 93     if(ql<=mid) maxx = max(maxx,query(q*2,l,mid,ql,qr));
 94     if(mid+1<=qr) maxx = max(maxx,query(q*2+1,mid+1,r,ql,qr));
 95     return maxx;
 96 }
 97 int main()
 98 {
 99     int T,kase = 0;cin>>T;
100     while(T--)
101     {
102         scanf("%d %d",&n,&m);
103         for(int i=0;i<=n;i++) g[i].clear();
104         int xx,xy;
105         for(int i=1;i<=n-1;i++)
106         {
107             scanf("%d %d",&xx,&xy);
108             g[xx].push_back(xy);
109             g[xy].push_back(xx);
110         }
111         for(int i=0;i<n;i++) scanf("%I64d",&w[i]);
112         index = 1;
113         memset(d,0,sizeof(d));
114         memset(vis,0,sizeof(vis));
115         memset(L,0,sizeof(L));
116         memset(R,0,sizeof(R));
117         d[1] = w[0];
118         vis[0] = 1;
119         dfs(0,1);
120         build(1,1,n);
121         printf("Case #%d:\n",++kase);
122         int x,y;
123         ll ttt;
124         for(int i=1;i<=m;i++)
125         {
126             scanf("%d %d",&x,&y);
127             if(x==1)
128             {
129                 printf("%I64d\n",query(1,1,n,L[y],R[y]));
130             }
131             else
132             {
133                 scanf("%I64d",&ttt);
134                 ll tt = ttt-w[y];
135                 ins(1,1,n,L[y],R[y],tt);
136                 w[y] = ttt;  //坑点
137             }
138         }
139     }
140     return 0;
141 }