BZOJ 1036 && Luogu P2590 [ZJOI2008]树的统计树链剖分

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

链剖裸题。。。你值得一做~

用线段树多维护一个mx，少写一个tag

#include<cstdio>

#include<iostream>

#define ll long long

#define R register ll

#define ls (tr<<1)

#define rs (tr<<1|1)

using namespace std;

const int N=;

inline ll g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

int n,m,cnt,num,mod;

int vr[N<<],nxt[N<<],fir[N],dfn[N],pre[N],son[N],d[N],sz[N],top[N],rw[N],w[N];

ll sum[N<<],mx[N<<];

inline void add(int u,int v) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}

void dfs(int u) { sz[u]=; R mx=;

    for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

        if(d[v]) continue; pre[v]=u; d[v]=d[u]+;

        dfs(v); sz[u]+=sz[v]; if(sz[v]>mx) son[u]=v,mx=sz[v];

    }

}

void dfs_(int u,int tp) {

    top[u]=tp,dfn[u]=++num,rw[num]=u;

    if(son[u]) dfs_(son[u],tp);

    for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

        if(v!=pre[u]&&v!=son[u]) dfs_(v,v);

    }

}

inline void build(int tr,int l,int r) {

    if(l==r) {mx[tr]=sum[tr]=w[rw[l]]; return ;}

    R md=(l+r)>>; build(ls,l,md),build(rs,md+,r);

    sum[tr]=sum[ls]+sum[rs],mx[tr]=max(mx[ls],mx[rs]);

}

inline ll queryS(int tr,int l,int r,int LL,int RR) {

    if(LL<=l&&r<=RR) return sum[tr]; R md=(l+r)>>,ret=;

    if(LL<=md) ret+=queryS(ls,l,md,LL,RR); if(RR>md) ret+=queryS(rs,md+,r,LL,RR);

    return ret;

}

inline ll queryM(int tr,int l,int r,int LL,int RR) {

    if(LL<=l&&r<=RR) return mx[tr]; R md=(l+r)>>,ret=-;

    if(LL<=md) ret=max(queryM(ls,l,md,LL,RR),ret); if(RR>md) ret=max(queryM(rs,md+,r,LL,RR),ret);

    return ret;

}

inline void update(int tr,int l,int r,int pos,ll inc) {

    if(l==r) {mx[tr]=sum[tr]=inc; return ;}

    R md=(l+r)>>; if(pos<=md) update(ls,l,md,pos,inc); else update(rs,md+,r,pos,inc);

    sum[tr]=sum[ls]+sum[rs],mx[tr]=max(mx[ls],mx[rs]);

}

inline ll queryTS(int u,int v) { R ret=;

    while(top[u]!=top[v]) {

        if(d[top[u]]<d[top[v]]) swap(u,v);

        ret+=queryS(,,n,dfn[top[u]],dfn[u]);

        u=pre[top[u]];

    } if(dfn[u]>dfn[v]) swap(u,v); ret+=queryS(,,n,dfn[u],dfn[v]);

    return ret;

}

inline ll queryTM(int u,int v) { R ret=-;

    while(top[u]!=top[v]) {

        if(d[top[u]]<d[top[v]]) swap(u,v);

        ret=max(queryM(,,n,dfn[top[u]],dfn[u]),ret);

        u=pre[top[u]];

    } if(dfn[u]>dfn[v]) swap(u,v); ret=max(queryM(,,n,dfn[u],dfn[v]),ret);

    return ret;

}

inline void print(int tr,int l,int r) {

    if(l==r) {printf("%lld %lld ",sum[tr],mx[tr]); return ;} R md=(l+r)>>;

    print(ls,l,md),print(rs,md+,r);

}

signed main() {

    n=g(); for(R i=,u,v;i<n;++i) u=g(),v=g(),add(u,v),add(v,u);

    for(R i=;i<=n;++i) w[i]=g();

    d[]=top[]=pre[]=; dfs(),dfs_(,); build(,,n); m=g();

    for(R i=;i<=m;++i) { register char ch;

        while(!isalpha(ch=getchar())); ch=getchar(); R u=g(),v=g();

        if(ch=='H') update(,,n,dfn[u],v);

        else if(ch=='M') printf("%lld\n",queryTM(u,v));

        else printf("%lld\n",queryTS(u,v));

    }

}