树链剖分_牛客博客

$不懂可以参考别人的博客\Uparrow$
$dfn是每个结点的dfs序，将树上的点映射到区间便于用线段树进行维护$
$id[x]=dfn，记录x的编号是dfn$
$一条重链上的点，编号连续，方便线段树维护$
$(1)同一重链上的点，他们最短路径上所有结点之和就是他们编号之间的区间和（如果都加上一个值同理）$
$不在同一条重链上，其实就是LCA$
$dep[x]表示结点x的深度$
$（假设结点x、y不在一条重链上，如果dep[top[x]]<dep[top[y]],swap(x,y)）$
$(2)加上x到所在重链起点编号之间的区间和，x跳到所在重链的起点的父结点上$
$top[x]表示x这条重链的起点，轻链没有起始点之说，这里用top[]加速$
$重复步骤(2)，直到x、y在一个重链上，然后执行步骤(1)$
$如果是要将树从x到y结点最短路径上所有节点的值都加上z，原理同上$
$如果是将以 x 为根节点的子树内所有节点值都加上 z就更轻松了，x结点和它子树上所有结点的编号是连续的$
$size[x]记录x为根的子树的结点数$
$以 x 为根节点的子树，在线段树对应的区间是[id[x],id[x]+size[x]-1]$
$rk[dfn]=x,记录编号dfn对应的结点是x，便于建树$

poj3384

$板子题$

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=2e5+7;
typedef long long ll;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int head[maxn],to[maxm],Next[maxm],tot;
int dep[maxn],f[maxn],size[maxn],son[maxn];
int top[maxn],id[maxn],rk[maxn],dfn;
int n,m,qi,mod,a[maxn];
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
void dfs1(int x) {
    size[x]=1,dep[x]=dep[f[x]]+1;
    for(int i=head[x],v;i;i=Next[i]) {
        v=to[i];
        if(v==f[x]) continue;
        f[v]=x;
        dfs1(v);
        size[x]+=size[v];
        if(size[son[x]]<size[v]) son[x]=v;
    }
}
void dfs2(int x,int tp) {
    top[x]=tp,id[x]=++dfn,rk[dfn]=x;
    if(son[x]) dfs2(son[x],tp);
    for(int i=head[x],v;i;i=Next[i]) {
        v=to[i];
        if(v==f[x]||v==son[x]) continue;
        dfs2(v,v);
    }
}
ll sum[maxn<<2],lazy[maxn<<2];
void push_down(int rt,int m) {
    if(lazy[rt]) {
        (lazy[rt<<1]+=lazy[rt])%=mod;
        (lazy[rt<<1|1]+=lazy[rt])%=mod;
        (sum[rt<<1]+=(m-(m>>1))*lazy[rt])%=mod;
        (sum[rt<<1|1]+=(m>>1)*lazy[rt])%mod;
        lazy[rt]=0;
    }
}
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void build(int l,int r,int rt) {
    lazy[rt]=0;
    if(l==r) {
        sum[rt]=a[rk[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    (sum[rt]=sum[rt<<1]+sum[rt<<1|1])%=mod;
}
void update(int a,int b,ll c,int l,int r,int rt){
    if(a<=l&&b>=r) {
        (sum[rt]+=(r-l+1)*c)%mod;
        (lazy[rt]+=c)%=mod;
        return;
    }
    push_down(rt,r-l+1);
    int mid=(l+r)>>1;
    if(a<=mid)    update(a,b,c,lson);
    if(b>mid)    update(a,b,c,rson);
    (sum[rt]=sum[rt<<1]+sum[rt<<1|1])%=mod;
}
ll query(int a,int b,int l,int r,int rt) {
    if(a<=l&&b>=r)    return sum[rt];
    push_down(rt,r-l+1);
    int mid=(l+r)>>1;
    ll ans=0;
    if(a<=mid)    ans+=query(a,b,lson);
    if(b>mid)    ans+=query(a,b,rson);
    return ans%mod;
}
void Subupdate(int x,int y,ll c) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        update(id[top[x]],id[x],c,1,n,1);
        x=f[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    update(id[x],id[y],c,1,n,1);
}
ll Subquery(int x,int y) {
    ll res=0;
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        (res+=query(id[top[x]],id[x],1,n,1))%=mod;
        x=f[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    return (res+query(id[x],id[y],1,n,1))%mod;
}
int main() {
    n=read(),m=read(),qi=read(),mod=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=2,u,v;i<=n;++i) {
        u=read(),v=read();
        add(u,v),add(v,u); 
    }
    dfs1(qi),dfs2(qi,qi);
    build(1,n,1);
    for(int i=1,op,x,y,z;i<=m;++i) {
        op=read(),x=read();
        if(op==1) {
            y=read(),z=read();
            Subupdate(x,y,z);
        }
        else if(op==2) {
            y=read();
            printf("%lld\n",Subquery(x,y));
        }
        else if(op==3) {
            z=read();
            update(id[x],id[x]+size[x]-1,z,1,n,1);
        }
        else printf("%lld\n",query(id[x],id[x]+size[x]-1,1,n,1));
    }
}

[NOI2015]软件包管理器

$删除结点x，需要改变安装状态的软件包数就是x子树已安装的软件包数ans1$
$安装结点x，需要改变安装状态的软件包数就是x到根节点未安装的软件包数ans2$
$涉及到0结点，son[]初始化为-1$
$0号软件包不依赖其它软件包，表示0是根，且依赖关系是有向图$
$求ans1后将区间[id[x],id[x]+size[x]-1]的和改为0$
$求ans2时，边查询x到根节点未安装的软件包数，边修改$
$将查到的每条重链的区间和修改为1*该重链的长度$
$lazy[]注意初始化为-1，而不是0，会出事$

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=1e5+7;
typedef long long ll;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int head[maxn],to[maxm],Next[maxm],tot;
int dep[maxn],f[maxn],size[maxn],son[maxn];
int top[maxn],id[maxn],rk[maxn],dfn;
int n;
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
void dfs1(int x) {
    size[x]=1,dep[x]=dep[f[x]]+1;
    for(int i=head[x],v;i;i=Next[i]) {
        v=to[i];
        f[v]=x;
        dfs1(v);
        size[x]+=size[v];
        if(son[x]==-1||size[son[x]]<size[v]) son[x]=v;
    }
}
void dfs2(int x,int tp) {
    top[x]=tp,id[x]=++dfn,rk[dfn]=x;
    if(~son[x]) dfs2(son[x],tp);
    for(int i=head[x],v;i;i=Next[i]) {
        v=to[i];
        if(v==son[x]) continue;
        dfs2(v,v);
    }
}
ll sum[maxn<<2],lazy[maxn<<2];
void push_down(int rt,int m) {
    if(lazy[rt]!=-1) {
        lazy[rt<<1]=lazy[rt];
        lazy[rt<<1|1]=lazy[rt];
        sum[rt<<1]=(m-(m>>1))*lazy[rt];
        sum[rt<<1|1]=(m>>1)*lazy[rt];
        lazy[rt]=-1;
    }
}
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void update(int a,int b,ll c,int l,int r,int rt){
    if(a<=l&&b>=r) {
        sum[rt]=(r-l+1)*c;
        lazy[rt]=c;
        return;
    }
    push_down(rt,r-l+1);
    int mid=(l+r)>>1;
    if(a<=mid)    update(a,b,c,lson);
    if(b>mid)    update(a,b,c,rson);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
ll query(int a,int b,int l,int r,int rt) {
    if(a<=l&&b>=r)    return sum[rt];
    push_down(rt,r-l+1);
    int mid=(l+r)>>1;
    ll ans=0;
    if(a<=mid)    ans+=query(a,b,lson);
    if(b>mid)    ans+=query(a,b,rson);
    return ans;
}
ll Subquery(int x,int y) {
    ll res=0,tmp;
    while(top[x]!=top[y]) { 
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        res+=id[x]-id[top[x]]+1-query(id[top[x]],id[x],1,n,1);
        update(id[top[x]],id[x],1,1,n,1);
        x=f[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    tmp=query(id[x],id[y],1,n,1);
    update(id[x],id[y],1,1,n,1);
    return res+id[y]-id[x]+1-tmp;
}
string s;
int main() {
    n=read();
    for(int i=1,u;i<n;++i) {
        u=read();
        add(u,i); 
    }
    memset(son,-1,sizeof son);//zhu yi
    memset(lazy,-1,sizeof lazy);
    dfs1(0),dfs2(0,0);
    int q=read();
    for(int i=1,x;i<=q;++i) {
        cin>>s;    x=read();
        if(s=="install") {
            cout<<Subquery(x,0)<<endl;
        }
        else {
            cout<<query(id[x],id[x]+size[x]-1,1,n,1)<<endl;
            update(id[x],id[x]+size[x]-1,0,1,n,1);
        }
    }
}