HDU 5692-Snacks(dfs序线段树)

$Description$
图片说明

$Solution$
处理出每个节点到根节点的node[u]值,对于修改操作相当于对子树中的node值修改,查找时查找子树的最大值即可.
dfs序转化成区间操作,线段树查找最大值.

$Code$

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define sc scanf
#define itn int
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=1e5+225;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=x*(a/b);}
int n,m,pos[N];
ll node[N],a[N],MAX[N<<2|1],tag[N<<2|1];
vector<int>g[N];
int in[N],out[N],tot=0;
void dfs(int u,int fa){
    node[u]+=node[fa];
    in[u]=++tot;
    pos[tot]=u;
    for(int v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    out[u]=tot;
}
void tree(int l,int r,int rt){
    tag[rt]=0;
    if(l>=r){
        MAX[rt]=node[pos[l]];
        return ;
    }
    int mid=l+r>>1;
    tree(l,mid,rt<<1);
    tree(mid+1,r,rt<<1|1);
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
void pu(int rt){
    if(tag[rt]!=0){
        MAX[rt<<1]+=tag[rt];
        MAX[rt<<1|1]+=tag[rt];
        tag[rt<<1]+=tag[rt];
        tag[rt<<1|1]+=tag[rt];
    }
    tag[rt]=0;
}
void ins(int l,int r,int rt,int L,int R,int val){
    if(L<=l&&r<=R){
        MAX[rt]+=val;
        tag[rt]+=val;
        return ;
    }
    pu(rt);
    int mid=l+r>>1;
    if(mid>=L)ins(l,mid,rt<<1,L,R,val);
    if(mid<R)ins(mid+1,r,rt<<1|1,L,R,val);
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
ll Q(int l,int r,int rt,int L,int R){
    if(L<=l&&r<=R)return MAX[rt];
    pu(rt);
    int mid=l+r>>1;
    ll M=-1e18;
    if(mid>=L)M=max(M,Q(l,mid,rt<<1,L,R));
    if(mid<R)M=max(M,Q(mid+1,r,rt<<1|1,L,R));
    return M;
}
int main(){
    int t;cin>>t;
    for(int cas=1;cas<=t;cas++){
        tot=0;
        sc("%d%d",&n,&m);
        for(int i=0;i<=n+5;i++)g[i].clear();
        for(int i=1;i<n;i++){
            int u,v;
            sc("%d%d",&u,&v);
            u++,v++;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for(int i=1;i<=n;i++)sc("%lld",node+i),a[i]=node[i];
        dfs(1,0);
        tree(1,n,1);
        printf("Case #%d:\n",cas);
        while(m--){
            int op;sc("%d",&op);
            if(op==0){
                int x,y;
                sc("%d%d",&x,&y);x++;
                y-=a[x];a[x]+=y;
                ins(1,n,1,in[x],out[x],y);
            }else{
                int x;sc("%d",&x);x++;
                printf("%lld\n",Q(1,n,1,in[x],out[x]));
            }
        }
    }
}