洛谷4211 [LNOI2014]LCA

access_time    bookmark 题解    comment 0 条评论    NOI/NOI+/CTSC

题意

给出一棵树,定义 $\mathrm{dep}[i]$ 为 $i$ 的深度,$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。

有形如 $\text{(l r z)}$ 的询问,求 $\sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]$ 。

其中点数 $N\le 50000$ ,询问数 $M\le 50000$ 。

题解

用暴力求 $\mathrm{LCA}$ 时,我们可以标记其中一个节点到根节点的路径,剩下一个节点向上走,遇到标记的节点即是 $\mathrm{LCA}$ 。

而一个节点的深度可以认为是它到根节点的距离,令 $1$ 为根,那么求 $\mathrm{LCA(i,j)}$ 的深度可以转化为:将路径 $(1,i)$ 上的节点权值都 $+1$ ,然后查询路径 $(1,j)$ 上的权值和。

考虑差分,将 $[l,r]$ 转化为 $[1,r]-[1,l-1]$ 。我们可以从 $1$ 开始对每个节点到根节点的路径上的权值 $+1$ ,遇到询问再查询路径 $(1,z)$ 上的权值和。

具体实现是将 $l$ 和 $r$ 分开储存,并进行排序。然后从小到大扫一遍,遇到需要查询的就进行查询,然后计算对答案的贡献。

我是把 $l-1$ 存在奇数下标里,把 $r$ 存在偶数下标里,所以对答案的贡献即为 $(-2\times (i \mod 2)+1)\times now$ 。其中 $i$ 是原先的下标, $now$ 是当前查询到的值。

#include<bits/stdc++.h>
#define ha 201314

using namespace std;

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

struct Edge {
    int next,to;
} edge[50005];
struct Tree {
    int left,right,sum,delta;
} tree[200005];
struct Q {
    int i,pos,z;
} q[100005];
int cnt,head[50005],n,m,a,b,c,ans[50005];
int dfsord,siz[50005],fa[50005],son[50005],deep[50005],top[50005],id[50005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void pushup(int x) { tree[x].sum=(tree[x*2].sum+tree[x*2+1].sum)%ha; }

inline void pushdown(int x)
{
    tree[x*2].sum=(tree[x*2].sum+tree[x].delta*(tree[x*2].right-tree[x*2].left))%ha;
    tree[x*2+1].sum=(tree[x*2+1].sum+tree[x].delta*(tree[x*2+1].right-tree[x*2+1].left))%ha;
    tree[x*2].delta=(tree[x*2].delta+tree[x].delta)%ha;
    tree[x*2+1].delta=(tree[x*2+1].delta+tree[x].delta)%ha;
    tree[x].delta=0;
}

void build(int x,int l,int r)
{
    tree[x].left=l;
    tree[x].right=r;
    if (r-l>1)
    {
        int mid=(l+r)>>1;
        build(x*2,l,mid);
        build(x*2+1,mid,r);
    }
}

void update(int x,int l,int r,int delta)
{
    if (l<=tree[x].left && r>=tree[x].right)
    {
        tree[x].sum=(tree[x].sum+delta*(tree[x].right-tree[x].left))%ha;
        tree[x].delta=(tree[x].delta+delta)%ha;
    }
    else
    {
        if (tree[x].delta) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) update(x*2,l,r,delta);
        if (r>mid) update(x*2+1,l,r,delta);
        pushup(x);
    }
}

int query(int x,int l,int r)
{
    if (l<=tree[x].left && r>=tree[x].right) return tree[x].sum;
    else
    {
        if (tree[x].delta) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1,ans=0;
        if (l<mid) ans=(ans+query(x*2,l,r))%ha;
        if (r>mid) ans=(ans+query(x*2+1,l,r))%ha;
        return ans;
    }
}

void dfs1(int x,int f,int dep)
{
    fa[x]=f;
    deep[x]=dep;
    siz[x]=1;
    int mx=0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs1(y,x,dep+1);
        siz[x]+=siz[y];
        if (siz[x]>mx)
        {
            mx=siz[x];
            son[x]=y;
        }
    }
}

void dfs2(int x,int topf)
{
    top[x]=topf;
    id[x]=++dfsord;
    if (!son[x]) return;
    dfs2(son[x],topf);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}

inline void upRange(int u,int v,int delta)
{
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        update(1,id[top[u]],id[u]+1,delta);
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    update(1,id[u],id[v]+1,delta);
}

inline int qRange(int u,int v)
{
    int ans=0;
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        ans=(ans+query(1,id[top[u]],id[u]+1))%ha;
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    ans=(ans+query(1,id[u],id[v]+1))%ha;
    return ans;
}

inline bool cmp(Q x,Q y) { return x.pos<y.pos; } // 按位置先后排序

int main()
{
    n=read(); m=read();
    for (int i=1;i<n;i++)
    {
        a=read();
        add(a+1,i+1);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n+1);
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read()+1; c=read()+1; // 因为是 l-1 所以不 +1
        q[i*2-1].i=i*2-1; q[i*2].i=i*2;
        q[i*2-1].pos=a; q[i*2].pos=b;
        q[i*2-1].z=q[i*2].z=c;
    }
    m<<=1;
    sort(q+1,q+m+1,cmp);
    int j=0;
    for (int i=1;i<=m;i++)
    {
        while (j<q[i].pos) upRange(1,++j,1);
        int now=qRange(1,q[i].z);
        ans[(q[i].i+1)>>1]+=((q[i].i%2)*-2+1)*now;
        ans[(q[i].i+1)>>1]=(ans[(q[i].i+1)>>1]+ha)%ha;
    }
    m>>=1;
    for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交的评论将在审核后显示。