[LNOI2014]LCA

可以发现，问题能够转化为从询问点到根都加1，然后询问l到r的点到根的路径上权值之和。
然后这个问题又和“l到r的点到根路径上所有点权值分别+1，求询问点到根路径上的权值之和”等价。
进一步，发现询问是可减的，即等价于ans[r]-ans[l-1]。
把询问按编号排序
用树链剖分+线段树实现链修改+链查询。
边修改边回答询问即可。
注意答案要对201314取模。

#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define N 220000
#define eps 1e-7
#define inf 1e9+7
#define ll long long
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch==‘-‘)flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}
    return x*flag;
}
struct edge
{
    int to,nxt;
}e[N];
int num,head[N];
inline void add(int x,int y)
{
    e[++num]=(edge){y,head[x]};
    head[x]=num;
}
struct node
{
    int x,t,id,flag;
}p[N];
bool cmp(node a,node b)
{
    return a.t<b.t;
}
struct Segment_Tree
{
    #define lson o<<1
    #define rson o<<1|1
    #define mid ((l+r)>>1)
    int addv[N*4],sumv[N*4];
    inline void pushup(int o)
    {
        sumv[o]=sumv[lson]+sumv[rson];
    }
    inline void color(int o,int l,int r,int num)
    {
        addv[o]+=num;
        sumv[o]+=(r-l+1)*num;
    }
    inline void pushdown(int o,int l,int r)
    {
        color(lson,l,mid,addv[o]);
        color(rson,mid+1,r,addv[o]);
        addv[o]=0;
    }
    int query(int o,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr)return sumv[o];
        pushdown(o,l,r);
        int ans=0;
        if(ql<=mid)ans+=query(lson,l,mid,ql,qr);
        if(qr>mid)ans+=query(rson,mid+1,r,ql,qr);
        return ans; 
    }
    void optadd(int o,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr)
        {
            color(o,l,r,1);
            return;
        }
        pushdown(o,l,r);
        if(ql<=mid)optadd(lson,l,mid,ql,qr);
        if(qr>mid)optadd(rson,mid+1,r,ql,qr);
        pushup(o);
    }
}T;
int n,m,q,times,id[N],fa[N],sz[N],son[N],dep[N],top[N],ans[N];
void dfs1(int x,int t)
{
    sz[x]=1;dep[x]=t;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int to=e[i].to;
        dfs1(to,t+1);
        fa[to]=x;sz[x]+=sz[to];
        if(sz[son[x]]<sz[to])son[x]=to;
    }
}
void dfs2(int x,int tp)
{
    top[x]=tp;id[x]=++times;
    if(son[x])dfs2(son[x],tp);
    for(int i=head[x];i;i=e[i].nxt)
    {
        int to=e[i].to;
        if(to==son[x])continue;
        dfs2(to,to);
    }
}
int qrange(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans+=T.query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans+=T.query(1,1,n,id[x],id[y]);
    return ans;
}
void optrange(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        T.optadd(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    T.optadd(1,1,n,id[x],id[y]);
    return;
}
int main()
{
    int i,j,l,r,x;
    n=read();q=read();
    for(i=2;i<=n;i++)add(read()+1,i);
    dfs1(1,1);dfs2(1,1);
    for(i=1;i<=q;i++)
    {
        l=read()+1;r=read()+1;x=read()+1;
        p[++m]=(node){x,l-1,i,-1};
        p[++m]=(node){x,r+0,i,+1};
    }
    sort(p+1,p+m+1,cmp);
    for(i=1,j=0;i<=m;i++)
    {
        while(j<n&&j<p[i].t)optrange(1,++j);
        ans[p[i].id]+=p[i].flag*qrange(1,p[i].x);
    }
    for(i=1;i<=q;i++)printf("%d\n",ans[i]%201314);
    return 0;
}

[LNOI2014]LCA

原文：https://www.cnblogs.com/Creed-qwq/p/10068805.html