P4211

Aryper · 2021-08-19 17:09:40 · 个人记录

[LNOI2014]LCA

还是有相当思维难度的一道好题。

不过没有暴力分，并不明白这个数据规模的分层是用来干什么的。

考虑一种简单的情况，lca(i,z)=t，那么我们知道，t 一定在 i 到根节点的路径上，也一定在 z 到根节点的路径上。

那么假如说我们将从 i 到根节点的路径全部做上标记，那么从 z 向根节点搜索的路径的权值之和，就是 t 的深度。

那么现在就好玩了，我们将 i\in[l,r] 的所有 i 到根节点的路径都做上可累加的标记，再询问从 z 到根节点的权值之和即可。

但问题是，我们如果暴力这样做，甚至不如倍增 LCA 快。

我们再挖掘一个性质，对于节点 z，若询问是 [0,l-1]，我们得到了一个答案；若询问是 [0,r]，我们又得到了一个答案。那么现在，[l,r] 的答案是否是这两个答案相减？答案是肯定的，想一想大概就明白了。

那么这样，我们的离线就有了思路。

对于每个询问 [l,r]，我们在 l-1 和 r 分别做上区间左端点（减）和区间右端点（加）的标记。那么从 0 到 n-1 依次做上该点到根节点路径上的累加标记。同时，如果遇到询问标记，将答案统计进去即可。

修改路径权值和求路径权值是树链剖分的基本操作。

时间复杂度 O(m\log^2n)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cstdlib>
#define ll long long
using namespace std;

const ll N=5e4,mo=201314;

ll n,m,tot,cnt,x;

ll head[N+5],ver[N*2+5],nxt[N*2+5];

ll hs[N+5],id[N+5],fa[N+5],dt[N+5],siz[N+5],top[N+5];

vector<ll> flgl[N+5],flgr[N+5];

struct node{
    ll l,r,z,ans;
}q[N+5];

struct sgt{
    ll l,r,dat,laz;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define dat(x) tree[x].dat
    #define laz(x) tree[x].laz
}tree[N*4+5];

void build(ll p,ll l,ll r) {
    l(p)=l;r(p)=r;
    if(l==r) return;
    ll mid=(l+r)>>1;
    build(p*2,l,mid);build(p*2+1,mid+1,r);
}

void spread(ll p) {
    if(laz(p)) {
        dat(p*2)=(dat(p*2)+laz(p)*(r(p*2)-l(p*2)+1))%mo;
        laz(p*2)=(laz(p*2)+laz(p))%mo;
        dat(p*2+1)=(dat(p*2+1)+laz(p)*(r(p*2+1)-l(p*2+1)+1))%mo;
        laz(p*2+1)=(laz(p*2+1)+laz(p))%mo;
        laz(p)=0;
    }
}

ll query(ll p,ll l,ll r) {
    if(l<=l(p)&&r>=r(p)) return dat(p)%mo;
    spread(p);
    ll mid=(l(p)+r(p))>>1,res=0;
    if(l<=mid) res+=query(p*2,l,r);
    if(r>mid) res+=query(p*2+1,l,r);
    return res%mo;
}

void chg(ll p,ll l,ll r) {
    if(l<=l(p)&&r>=r(p)) {
        laz(p)=(laz(p)+1)%mo;
        dat(p)=(dat(p)+r(p)-l(p)+1)%mo;
        return;
    }
    spread(p);
    ll mid=(l(p)+r(p))>>1;
    if(l<=mid) chg(p*2,l,r);
    if(r>mid) chg(p*2+1,l,r);
    dat(p)=(dat(p*2)+dat(p*2+1))%mo;
}

void dfs(ll p,ll fath) {
    dt[p]=dt[fath]+1;fa[p]=fath;siz[p]=1;
    ll ma=0;
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==fath) continue;
        dfs(ver[i],p);siz[p]+=siz[ver[i]];
        if(siz[ver[i]]>ma) {
            hs[p]=ver[i];ma=siz[ver[i]];
        }
    }
}

void _dfs(ll p,ll topf) {
    id[p]=++cnt;top[p]=topf;
    if(!hs[p]) return;
    _dfs(hs[p],topf);
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==fa[p]||ver[i]==hs[p]) continue;
        _dfs(ver[i],ver[i]);
    }
}

void chgpath(ll x,ll y) {
    while(top[x]!=top[y]) {
        if(dt[top[x]]<dt[top[y]]) swap(x,y);
        chg(1,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dt[x]>dt[y]) swap(x,y);
    chg(1,id[x],id[y]);
}

ll qpath(ll x,ll y) {
    ll ans=0;
    while(top[x]!=top[y]) {
        if(dt[top[x]]<dt[top[y]]) swap(x,y);
        ans=(ans+query(1,id[top[x]],id[x]))%mo;
        x=fa[top[x]];
    }
    if(dt[x]>dt[y]) swap(x,y);
    ans=(ans+query(1,id[x],id[y]))%mo;
    return ans;
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();

    for(ll i=1;i<n;i++) {
        x=read();add(x,i);add(i,x);
    }

    dfs(0,n);_dfs(0,0);

    build(1,1,n);

    for(ll i=1;i<=m;i++) {
        q[i].l=read();q[i].r=read();q[i].z=read();
        if(q[i].l>0) flgl[q[i].l-1].push_back(i);
        flgr[q[i].r].push_back(i);
    }

    for(ll i=0;i<n;i++) {
        chgpath(i,0);
        for(ll j=0;j<flgl[i].size();j++) {
            q[flgl[i][j]].ans=(q[flgl[i][j]].ans-qpath(q[flgl[i][j]].z,0)+mo)%mo;
        }
        for(ll j=0;j<flgr[i].size();j++) {
            q[flgr[i][j]].ans=(q[flgr[i][j]].ans+qpath(q[flgr[i][j]].z,0))%mo;
        }
    }

    for(ll i=1;i<=m;i++) {
        write(q[i].ans);putchar('\n');
    }

    return 0;
}