hdu5692 (dfs序＋线段树)

忘记初始化mle n次 GG

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define pb(a) push_back(a)
using namespace std;
typedef long long ll;
const int N=100001;
vector<int> q[N];
ll dis[N];
int rk[N],tim,l[N],r[N],a[N];
void dfs(int u,int pre)
{
    tim++;
    rk[tim]=u;
    l[u]=tim;
    for(int i=0;i<q[u].size();i++)
    {
        int v=q[u][i];
        if(v!=pre)
        {
            dis[v]=dis[u]+a[v];
            dfs(v,u);
        }
    }
    r[u]=tim;
}
ll sum[N<<2],lazy[N<<2];
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
void up(int rt)
{
    sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
void down(int rt)
{
    if(lazy[rt])
    {
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        sum[rt<<1]+=lazy[rt];
        sum[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    lazy[rt]=0;
    if(l==r)
    {
        sum[rt]=dis[rk[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(ls);
    build(rs);
    up(rt);
}
void update(int L,int R,ll val,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        lazy[rt]+=val;
        sum[rt]+=val;
        return;
    }
    int mid=(l+r)>>1;
    down(rt);
    if(L<=mid) update(L,R,val,ls);
    if(mid<R) update(L,R,val,rs);
    up(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return sum[rt];
    int mid=(l+r)>>1;
    down(rt);
    ll ans=-1e18;
    if(L<=mid) ans=max(ans,query(L,R,ls));
    if(mid<R) ans=max(query(L,R,rs),ans);
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        printf("Case #%d:\n",cas);
        int n,m,u,v;tim=0;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            q[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            q[u].pb(v);
            q[v].pb(u);
        }
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        dis[0]=a[0];
        dfs(0,-1);
        build(1,n,1);
        int cmd;
        while(m--)
        {
            scanf("%d",&cmd);
            if(cmd)
            {
                scanf("%d",&u);
                printf("%lld\n",query(l[u],r[u],1,n,1));
            }
            else
            {
                scanf("%d%d",&u,&v);
                update(l[u],r[u],v-a[u],1,n,1);
                a[u]=v;
            }
        }
    }
}