洛谷3384&bzoj1036树链剖分

值得注意的是：

一个点的子树是存在一起的。。。也就是说我们修改子树的时候只用。。。

/**************************************************************

    Problem: 1036

    User: Ez3real

    Language: C++

    Result: Accepted

    Time:3068 ms

    Memory:8112 kb

****************************************************************/

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#define l(x) (x<<1)

#define r(x) ((x<<1)|1)

#define ll long long

using namespace std;

struct Treenode{int l,r;ll tag,val,mx;};

struct Segtree

{

    Treenode tr[*];

    void pushup(int id){tr[id].val=tr[l(id)].val+tr[r(id)].val;}

    void pushdown(int id)

    {

        tr[l(id)].val+=tr[id].tag*(tr[l(id)].r-tr[l(id)].l+);

        tr[r(id)].val+=tr[id].tag*(tr[r(id)].r-tr[r(id)].l+);

        tr[l(id)].tag+=tr[id].tag;tr[r(id)].tag+=tr[id].tag;

        tr[id].tag=;

    }

    void build(int id,int L,int R)

    {

        tr[id].l=L,tr[id].r=R;

        tr[id].tag=;

        if(L==R)return;

        int mid=(L+R)>>;

        build(l(id),L,mid);

        build(r(id),mid+,R);

        pushup(id);

    }

    void update(int id,int L,int R,ll k)

    {

        if(tr[id].l>=L && tr[id].r<=R)

        {

            tr[id].val+=k*(tr[id].r-tr[id].l+);

            tr[id].tag+=k;

            return;

        }

        if(tr[id].tag)pushdown(id);

        int mid=(tr[id].l+tr[id].r)>>;

        if(L<=mid)update(l(id),L,R,k);

        if(R>mid) update(r(id),L,R,k);

        pushup(id);

    }

    ll query(int id,int L,int R)

    {

        if(tr[id].l>=L && tr[id].r<=R)return tr[id].val;

        if(tr[id].tag)pushdown(id);

        int mid=(tr[id].l+tr[id].r)>>;

        ll ans=;

        if(L<=mid)ans+=query(l(id),L,R);

        if(R>mid)ans+=query(r(id),L,R);

        return ans;

    }

}Seg;

int first[],to[*],next[*];

ll val[*],cnt;

int size[],depth[],fa[],pos[],bl[],sz;

inline void add(int u,int v){to[++cnt]=v;next[cnt]=first[u];first[u]=cnt;}

int n,q,r,P;

inline void dfs1(int u)

{

    size[u]=;

    for(int i=first[u];i;i=next[i])

    {

        if(to[i]==fa[u])continue;

        depth[to[i]]=depth[u]+;

        fa[to[i]]=u;

        dfs1(to[i]);

        size[u]+=size[to[i]];

    }

}

inline void dfs2(int u,int idc)

{

    int k=;

    sz++;

    pos[u]=sz;

    bl[u]=idc;

    for(int i=first[u];i;i=next[i])

        if(depth[to[i]]>depth[u] && size[to[i]]>size[k])

            k=to[i];

    if(k==)return;

    dfs2(k,idc);

    for(int i=first[u];i;i=next[i])

        if(depth[to[i]]>depth[u] && k!=to[i])

            dfs2(to[i],to[i]);

}

void tradd(ll x,ll v){Seg.update(,pos[x],pos[x]+size[x]-,v);}

ll trq(ll x){return Seg.query(,pos[x],pos[x]+size[x]-)%P;}

void Chainadd(ll x,ll y,ll v)

{

    while(bl[x]!=bl[y])

    {

        if(depth[bl[x]]<depth[bl[y]]){x^=y;y^=x;x^=y;}

        Seg.update(,pos[bl[x]],pos[x],v);

        x=fa[bl[x]];

    }

    if(depth[x]<depth[y]){x^=y;y^=x;x^=y;}

    Seg.update(,pos[y],pos[x],v);

}

ll Qsum(ll u,ll v)

{

    ll sum=;

    while(bl[u]!=bl[v])

    {

        if(depth[bl[u]]<depth[bl[v]]){u^=v;v^=u;u^=v;}

        (sum+=Seg.query(,pos[bl[u]],pos[u]))%=P;

        u=fa[bl[u]];

    }

    if(depth[u]<depth[v]){u^=v;v^=u;u^=v;}

    (sum+=Seg.query(,pos[v],pos[u]))%=P;

    return sum;

}

void Solve()

{

    scanf("%d%d%d%d",&n,&q,&r,&P);

    for(int i=;i<=n;i++)scanf("%lld",&val[i]);

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

    {

        int x,y;

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

        add(x,y);

        add(y,x);

    }

    depth[r]=;

    dfs1(r);

    dfs2(r,r);

    Seg.build(,,n);

    for(int i=;i<=n;i++)Seg.update(,pos[i],pos[i],val[i]);

    for(int i=;i<=q;i++)

    {

        int opt;

        scanf("%d",&opt);

        if(opt==)

        {

            ll x,y,w;

            scanf("%lld%lld%lld",&x,&y,&w);

            Chainadd(x,y,w);

        }

        if(opt==)

        {

            ll x,y;

            scanf("%lld%lld",&x,&y);

            printf("%lld\n",Qsum(x,y));

        }

        if(opt==)

        {

            ll x,v;

            scanf("%lld%lld",&x,&v);

            tradd(x,v);

        }

        if(opt==)

        {

            ll x;

            scanf("%lld",&x);

            printf("%lld\n",trq(x));

        }

    }

}

int main()

{

    Solve();

    return ;

}

Luogu3384

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#define l(x) (x<<1)

#define r(x) ((x<<1)|1)

#define ll long long

using namespace std;

struct Treenode{int l,r;ll tag,val,mx;};

struct Segtree

{

    Treenode tr[*];

    void pushup(int id){tr[id].val=tr[l(id)].val+tr[r(id)].val;tr[id].mx=max(tr[l(id)].mx,tr[r(id)].mx);}

    void build(int id,int L,int R)

    {

        tr[id].l=L,tr[id].r=R;

        if(L==R)return;

        int mid=(L+R)>>;

        build(l(id),L,mid);

        build(r(id),mid+,R);

        pushup(id);

    }

    void update(int k,int x,int y)

    {

        int l=tr[k].l,r=tr[k].r,mid=(l+r)>>;

        if(l==r){tr[k].val=tr[k].mx=y;return;}

        if(x<=mid)update(k<<,x,y);

        else update(k<<|,x,y);

        tr[k].val=tr[k<<].val+tr[k<<|].val;

        tr[k].mx=max(tr[k<<].mx,tr[k<<|].mx);

    }

    int query(int id,int L,int R)

    {

        if(tr[id].l>=L && tr[id].r<=R)return tr[id].val;

        int mid=(tr[id].l+tr[id].r)>>;

        int ans=;

        if(L<=mid)ans+=query(l(id),L,R);

        if(R>mid)ans+=query(r(id),L,R);

        return ans;

    }

    int Query(int id,int L,int R)

    {

        if(tr[id].l>=L && tr[id].r<=R)return tr[id].mx;

        int mid=(tr[id].l+tr[id].r)>>;

        int ans=-;

        if(L<=mid)ans=max(ans,Query(l(id),L,R));

        if(R>mid)ans=max(ans,Query(r(id),L,R));

        return ans;

    }

}Seg;

int first[],to[*],next[*],val[*],cnt;

int size[],depth[],fa[],pos[],bl[],sz;

inline void add(int u,int v){to[++cnt]=v;next[cnt]=first[u];first[u]=cnt;}

inline void dfs1(int u)

{

    size[u]=;

    for(int i=first[u];i;i=next[i])

    {

        if(to[i]==fa[u])continue;

        depth[to[i]]=depth[u]+;

        fa[to[i]]=u;

        dfs1(to[i]);

        size[u]+=size[to[i]];

    }

}

inline void dfs2(int u,int idc)

{

    int k=;

    sz++;

    pos[u]=sz;

    bl[u]=idc;

    for(int i=first[u];i;i=next[i])

        if(depth[to[i]]>depth[u] && size[to[i]]>size[k])

            k=to[i];

    if(k==)return;

    dfs2(k,idc);

    for(int i=first[u];i;i=next[i])

        if(depth[to[i]]>depth[u] && k!=to[i])

            dfs2(to[i],to[i]);

}

int Qsum(int u,int v)

{

    int sum=;

    while(bl[u]!=bl[v])

    {

        if(depth[bl[u]]<depth[bl[v]]){u^=v;v^=u;u^=v;}

        sum+=Seg.query(,pos[bl[u]],pos[u]);

        u=fa[bl[u]];

    }

    if(pos[u]>pos[v]){u^=v;v^=u;u^=v;}

    sum+=Seg.query(,pos[u],pos[v]);

    return sum;

}

int Qmax(int u,int v)

{

    int mx=-;

    while(bl[u]!=bl[v])

    {

        if(depth[bl[u]]<depth[bl[v]]){u^=v;v^=u;u^=v;}

        mx=max(mx,Seg.Query(,pos[bl[u]],pos[u]));

        u=fa[bl[u]];

    }

    if(pos[u]>pos[v]){u^=v;v^=u;u^=v;}

    mx=max(mx,Seg.Query(,pos[u],pos[v]));

    return mx;

}

int n,q;

void Solve()

{

    scanf("%d",&n);

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

    {

        int x,y;

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

        add(x,y);

        add(y,x);

    }

    for(int i=;i<=n;i++)scanf("%d",&val[i]);

    dfs1();

    dfs2(,);

    Seg.build(,,n);

    for(int i=;i<=n;i++)Seg.update(,pos[i],val[i]);

    scanf("%d",&q);

    char ch[];

    for(int i=;i<=q;i++)

    {

        int x,y;scanf("%s%d%d",ch,&x,&y);

        if(ch[]=='C'){val[x]=y;Seg.update(,pos[x],y);}

        else

        {

            if(ch[]=='M')printf("%d\n",Qmax(x,y));

            else printf("%d\n",Qsum(x,y));

        }

    }

}

int main()

{

    Solve();

    return ;

}

bzoj1036