[lnoi2014] LCA - tree chain subdivision - multipoint LCA depth and problems

Templates ： Topic link
Advanced ： Topic link

The question ：

Given a tree $n$ A dot tree .$q$ Time to ask , Each query gives three values $l,r,z$, Ask for ${\sum }_{i=l}^{r}dep(LCA(i,z))$.
$(n<=1e5,q<=1e5)$

Ideas ：

Consider asking for some $a$ Sum point $b$ Of $LCA$ depth , We can put some $a$ To $root$ All points on the path are weighted $1$, Then query points $b$ To $root$ Their path and are their $LCA$ Depth . Modify... In reverse $b$ To $root$ The path of , check $a$ To $root$ The path and are the same .

Then consider multiple points and single points $LCA$ Depth and , You can take each point to $root$ All paths add $1$, Then query a single point to $root$ The path and .

This becomes the operation of tree chain modification and query , You can use tree chain partition to maintain .

But this question can't be asked every time $o((r-l)lo{g}^{2}n)$ Modification of , So we need to find the prefix sum offline , Just take the prefix and subtract it again . Total complexity $o((n+q)lo{g}^{2}n)$.

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=201314;
typedef pair<ll,ll> P;
ll tree[1000005],laz[1000005];
void push_down(ll k,ll l,ll r)
{
    
    ll mid=(l+r)/2;
    tree[2*k+1]+=laz[k]*(mid-l+1);
    laz[2*k+1]+=laz[k];
    tree[2*k+2]+=laz[k]*(r-mid);
    laz[2*k+2]+=laz[k];
    laz[k]=0;
}
ll query(ll k,ll l,ll r,ll x,ll y)
{
    
    if(x<=l&&r<=y)
    {
    
        return tree[k];
    }
    push_down(k,l,r);
    ll ans=0,mid=(l+r)/2;
    if(x<=mid)ans+=query(2*k+1,l,mid,x,y);
    if(y>=mid+1)ans+=query(2*k+2,mid+1,r,x,y);
    return ans;
}
void update(ll k,ll l,ll r,ll x,ll y,ll a)
{
    
    if(x<=l&&r<=y)
    {
    
        tree[k]+=a*(r-l+1);
        laz[k]+=a;
        return ;
    }
    push_down(k,l,r);
    ll mid=(l+r)/2;
    if(x<=mid)update(2*k+1,l,mid,x,y,a);
    if(y>=mid+1)update(2*k+2,mid+1,r,x,y,a);
    tree[k]=tree[2*k+1]+tree[2*k+2];
}

vector<ll>v[100005];

ll dep[100005],fa[100005],siz[100005],son[100005];
void dfs1(ll x,ll pre)
{
    
    siz[x]=1;
    dep[x]=dep[pre]+1;
    fa[x]=pre;
    for(ll i=0;i<v[x].size();i++)
    {
    
        ll to=v[x][i];
        if(to!=pre)
        {
    
            dfs1(to,x);
            siz[x]+=siz[to];
        }
    }
    son[x]=x;
    for(ll i=0;i<v[x].size();i++)
    {
    
        ll to=v[x][i];
        if(to!=pre)
        {
    
            if(son[x]==x||siz[son[x]]<siz[to])son[x]=to;
        }
    }
}

ll id[100005],idx,top[100005];
void dfs2(ll x,ll pre)
{
    
    if(son[pre]==x)top[x]=top[pre];
    else top[x]=x;
    id[x]=++idx;
    if(son[x]!=x)dfs2(son[x],x);
    for(ll i=0;i<v[x].size();i++)
    {
    
        ll to=v[x][i];
        if(to!=pre&&to!=son[x])
        {
    
            dfs2(to,x);
        }
    }
}

ll n,m;
void add(ll x,ll val)
{
    
    while(top[x]!=1)
    {
    
        update(1,1,n,id[top[x]],id[x],val);
        x=fa[top[x]];
    }
    update(1,1,n,id[top[x]],id[x],val);
}
ll get(ll x)
{
    
    if(x==0)return 0;
    ll ans=0;
    while(top[x]!=1)
    {
    
        ans+=query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    ans+=query(1,1,n,id[top[x]],id[x]);
    return ans;
}

map<ll,ll>mp[100005];
vector<P>ve;
struct Q
{
    
    ll l,r,z;
}q[200005];


int main()
{
    
    scanf("%lld%lld",&n,&m);
    for(ll i=2;i<=n;i++)
    {
    
        ll a;
        scanf("%lld",&a);
        a++;
        v[a].push_back(i);
        v[i].push_back(a);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=m;i++)
    {
    
        ll l,r,z;
        scanf("%lld%lld%lld",&l,&r,&z);
        l++;r++;z++;
        q[i]=Q{
    l,r,z};
        ve.push_back(P(l-1,z));
        ve.push_back(P(r,z));
    }
    sort(ve.begin(),ve.end());
    int cnt=1;
    for(int i=0;i<ve.size();i++)
    {
    
        while(cnt<=n&&cnt<=ve[i].first)
        {
    
            add(cnt,1);
            cnt++;
        }
        mp[ve[i].first][ve[i].second]=get(ve[i].second)%mod;
    }
    for(int i=1;i<=m;i++)
    {
    
        ll l=q[i].l,r=q[i].r,z=q[i].z;
        ll ans=mp[r][z]-mp[l-1][z];
        printf("%lld\n",(ans%mod+mod)%mod);
    }
    return 0;
}