题解 P4211 【[LNOI2014]LCA】

题解-

• 窝，调了个上午发现被***错误困扰，总算调出来了。

• 题目意思

  题面很小清新：就是求

• 

  前置知识：树链剖分+差分

  考虑离线。

  我们首先可以把题目意思转换为：每次把询问区间里的点到根节点路径上的点权值（包括自己）加一，最后询问到根节点的权值和。我们可以画张图来理解这个转换。

  

  这样就和好理解了。那我们如何来处理这个询问呢。于是我们很自然地会想到差分，即把拆成。那我们怎么实现这个差分呢？我们只需要在点上打上标记（即代码中的），只要即可。区间加等操作我们可以用树链剖分套个线段树来求解（这很套路的）。

  时间复杂度：可以过得。

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int N=2e5+5;
const int mod=201314;

int n,m,cnt,head[N],id[N],top[N];
int son[N],laz[N<<2],tr[N<<2],res[N];
int ans,tot,f[N],dep[N],siz[N],all;

struct nood
{
    int nex,to;
};
nood e[N<<1];

struct question
{
    int pos,z,id,flg;
    inline bool friend operator < (const question &b,const question &c)
    {
        return b.pos<c.pos;
    }
};
question q[N<<1];

inline void jia(int u,int v)
{
    e[++cnt].nex=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}

inline void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    siz[u]=1;
    f[u]=fa;
    for ( int i=head[u];i;i=e[i].nex )
    {
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) 
            son[u]=v;
    }
}

inline void dfs2(int u,int tp)
{
    id[u]=++tot;
    top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    for ( int i=head[u];i;i=e[i].nex )
    {
        int v=e[i].to;
        if(v==f[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

inline void push_down(int rt,int l,int r)
{
    if(laz[rt])
    {
        laz[rt<<1]+=laz[rt];
        laz[rt<<1|1]+=laz[rt];
        int mid=(l+r)/2;
        tr[rt<<1]+=(mid-l+1)*laz[rt];
        tr[rt<<1|1]+=(r-mid)*laz[rt];
        laz[rt]=0;
    }
}

inline void update(int rt,int l,int r,int ll,int rr)
{
    if(ll<=l && rr>=r) 
    {
        laz[rt]+=1ll;
        tr[rt]+=(r-l+1);
        return;
    }
    push_down(rt,l,r);
    int mid=(l+r)/2;
    if(ll<=mid) update(rt<<1,l,mid,ll,rr);
    if(rr>mid) update(rt<<1|1,mid+1,r,ll,rr); 
    tr[rt]=(tr[rt<<1]+tr[rt<<1|1]);
}

inline int query(int rt,int l,int r,int ll,int rr)
{
    if(ll<=l && rr>=r) return tr[rt];
    push_down(rt,l,r);
    int mid=(l+r)/2;
    int ans=0;
    if(ll<=mid) ans+=query(rt<<1,l,mid,ll,rr);
    if(rr>mid) ans+=query(rt<<1|1,mid+1,r,ll,rr); 
    return ans;
}


inline void modify(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        update(1,1,n,id[top[u]],id[u]);
        u=f[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    update(1,1,n,id[u],id[v]);
}

inline int qsum(int u,int v)
{
    int ans=0 ;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        ans+=query(1,1,n,id[top[u]],id[u]);
        ans=(ans+mod)%mod;
        u=f[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    ans=(ans+query(1,1,n,id[u],id[v]))%mod;
    return ans;
}
//树链剖分套线段树

signed main()
{
//    freopen("mx.in","r",stdin);
//    freopen("my.out","w",stdout);
    n=read();
    m=read();
    f[1]=1,dep[1]=0,siz[0]=0;
    for ( int i=2;i<=n;++i )
    {
        int u=read()+1;
        //+1更加好处理
        jia(u,i);
        jia(i,u);
    }
    dfs(1,0);
    dfs2(1,0);
    for ( int i=1;i<=m;i++ )
    {
        int l=read()+1;
        int r=read()+1;
        int z=read()+1;
        q[all++]=(question){l-1,z,i,0};
        //对l-1进行标记
        q[all++]=(question){r,z,i,1};
    }
    sort(q,q+all);
    int cur =1;
    for( int i=0;i<all;++i)
    {
        while(cur<=q[i].pos) modify(1,cur++);
        if(q[i].flg) res[q[i].id]+=qsum(1,q[i].z);
        else res[q[i].id]-=qsum(1,q[i].z);
        res[q[i].id]+=mod;
        res[q[i].id]%=mod;
    }
    for ( int i=1;i<=m;++i)
        printf("%lld\n",res[i]);
    return 0;
}
/*
5 2
0
0
1
1
1 4 3
1 4 2
*/