bzoj 3626 [LNOI2014] LCA 题解

题意简述

给你一颗n<=1e5个节点树，1e5次询问，每次给你(l,r,z)，求[l,r]区间内每个数和z在树上LCA的深度的和。对201314取膜。

注：根节点深度是1。

思路框架

(x,y)的LCA深度就是，把x到根点权+1，然后询问根到y点权和多少。

那么我们相当于，把[l,r]每个点到根点权都+1，然后询问根到z的点权和。差分做。

具体思路

差分做法：把一个询问(l,r,z)拆成(1,r,z)和(1,l-1,z)。(l,r,z)的答案显然就是(1,r,z)-(1,l-1,z)。这样我们要求的就是若干的前缀点的答案了。

我们把l-1和r都打上标记i从1到n遍历一下，不断在根到i的路径上点权+1。的如果某个点有标记，那么就把所有的z拿出来询问一遍，更新询问的答案。这样是O(nlogn+q)。

还有，对于每个标记，还要记录是l-1还是r，因为l-1的答案还要带一个负号。

代码

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 54444
    #define mod 201314
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    class Graph //这个是图。跳到60行
    //如果你有个IDE，那么直接折叠起来好了
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Label,Next;
            }Ed[N<<3];
            void clear()
            {
                memset(head,-1,sizeof(head));
                memset(Ed,-1,sizeof(Ed));
                EdgeCount=0;
            }
    
            void AddEdge(int u,int v,int w=1)
            {
                ++EdgeCount;
                Ed[EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v,int w=1)
            {
                AddEdge(u,v,w);AddEdge(v,u,w);
            }
    
            int Start(int u)
            {
                return head[u];
            }
            int To(int u)
            {
                return Ed[u].To;
            }
            int Label(int u)
            {
                return Ed[u].Label;
            }
            int Next(int u)
            {
                return Ed[u].Next;
            }
    
    }G;
    class SegmentTree //这个是线段树。支持区间加Add(l,r,x)，还有区间求和Query(l,r)。
    //如果您会，跳到138行.
    {
    public:
        struct node
        {
            int l,r;
            int s,a;
        }tree[N<<2];
        #define ls index<<1
        #define rs index<<1|1

        #define L tree[index].l
        #define R tree[index].r
        #define S tree[index].s
        #define A tree[index].a

        #define lL tree[ls].l
        #define lR tree[ls].r
        #define lS tree[ls].s
        #define lA tree[ls].a

        #define rL tree[rs].l
        #define rR tree[rs].r
        #define rS tree[rs].s
        #define rA tree[rs].a
        void Update(int index=1)
        {
            S=(lS+rS)%mod;
        }
        void Build(int l,int r,int index=1)
        {
            L=l,R=r;
            if (l==r) 
            {
                S=0;return;
            }

            int mid=(l+r)>>1;
            Build(l,mid,ls);
            Build(mid+1,r,rs);
            Update(index);
        }
        void AddOne(int x,int index=1)
        {
            A+=x;
            S+=(R-L+1)*x;
            A%=mod,S%=mod;
        }
        void PushDown(int index=1)
        {
            if (A)
            {
                AddOne(A,ls);
                AddOne(A,rs);
                A=0;
            }
        }
        void Add(int l,int r,int x,int index=1)
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r) return AddOne(x,index);

            PushDown(index);
            Add(l,r,x,ls);
            Add(l,r,x,rs);
            Update(index);
        }
        int Query(int l,int r,int index=1)
        {
            if (l>R or L>r) return 0;
            if (l<=L and R<=r) return S;

            PushDown(index);
            return (Query(l,r,ls)+Query(l,r,rs))%mod;
        }
    }T;

    int n,q;
    struct node //一个询问
    {
        int l,r,z;
    }Q[N];
    vector<int> idl[N],idr[N];
    //l-1和r分开记录
    bool cxk[N];
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Input()
    {
        R1(n),R1(q);
        G.clear();
        F(i,2,n) 
        {
            int fa;R1(fa);++fa; //我们从1开始编号
            G.Add2(i,fa);
        } 

        F(i,1,q) 
        {
            int l,r,z;
            R1(l),R1(r),R1(z);
            ++l,++r,++z;

            Q[i]=(node){l,r,z};
            cxk[l-1]=cxk[r]=1; //记录该点是否有标记
            idl[l-1].push_back(i); 
            idr[r].  push_back(i); //记录标记
            //标记存询问的编号.询问中的l,r,z只要一个编号就都能获取了.
        }
    }

    int deep[N],size[N],fa[N],son[N];
    //如果您会树剖,跳到218行
    //这里两个DFS都是没有改过的模板
    void DFS(int u,int f)
    {
        deep[u]=(u==f)?1:deep[f]+1;
        size[u]=1;
        fa[u]=f;

        son[u]=-1;int Max=-1;
        Tra(i,u)
        {
            int v=__v;
            if (v!=f)
            {
                DFS(v,u);
                size[u]+=size[v];
                if (size[v]>Max)
                {
                    Max=size[v];
                    son[u]=v;
                }
            }
        }
    }
    int DFSid[N],Time=0;
    int top[N];
    void DFS2(int u,int topu)
    {
        top[u]=topu;
        DFSid[u]=++Time;

        if (son[u]==-1) return;
        DFS2(son[u],topu);
        Tra(i,u)
        {
            int v=__v;
            if (v!=son[u] and v!=fa[u])
            {
                DFS2(v,v);
            }
        }
    }
    //DFS1和DFS2是树剖用的函数

    void PathAdd(int u,int v) //u到v的链上点权+1
    {
        while(top[u]!=top[v])
        {
            if (deep[top[u]]<deep[top[v]]) swap(u,v);
            T.Add(DFSid[top[u]],DFSid[u],1);
            u=fa[top[u]];
        }
        if (deep[u]>deep[v]) swap(u,v);
        T.Add(DFSid[u],DFSid[v],1);
    }
    int PathQuery(int u,int v) //询问u到v上点权的和
    {
        int ans=0;
        while(top[u]!=top[v])
        {
            if (deep[top[u]]<deep[top[v]]) swap(u,v);
            ans+=T.Query(DFSid[top[u]],DFSid[u]);
            u=fa[top[u]];
        }
        if (deep[u]>deep[v]) swap(u,v);
        ans+=T.Query(DFSid[u],DFSid[v]);
        return ans;
    }
    //核心代码
    int ans[N]; //ans[i]: 第i个询问的答案
    void Soviet()
    {
        DFS(1,1);
        DFS2(1,1);
        T.Build(1,n); //记得建树
        F(i,1,n)
        {
            PathAdd(1,i); //从i到根(1)+1
            if (cxk[i]) //如果有标记
            {
                F(j,0,(int)idl[i].size()-1)
                {
                    int id=idl[i][j]; 
                    ans[id]-=PathQuery(1,Q[id].z); //l-1的询问答案是减掉的
                    ans[id]%=mod; 
                }
                F(j,0,(int)idr[i].size()-1) //r的答案是加上的
                {
                    int id=idr[i][j];
                    ans[id]+=PathQuery(1,Q[id].z);
                    ans[id]%=mod;
                }
            }
        }

        F(i,1,q)
        {
            printf("%d\n",(ans[i]%mod+mod)%mod);
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}