Loading...

洛谷P2420 让我们异或吧

check评论:0 条 remove_red_eye浏览量:428 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-07-10

树链剖分裸题

至于树链剖分,可以看这位大佬的博客

不过有一些问题,比如如何解决边权?

举个例子:

我们将边权赋值为一条边中深度较大的点的点权即可

查询时注意,如查询路径$a-b$,查询完所有链之后会发现多查询了一个$lca(a,b)$,我们就需要对其做一次异或的逆运算

因为异或具有交换律,即

$a$^$(b$^$c)$ $=$ $(a$^$b)$^$c$

故$a$^$(a$^$b)$ $=$ $(a$^$a)$^$b$

所以异或就是异或的逆运算,对答案再异或一次其$lca$值即可

然后进行树链剖分常规操作

关于$lca$,也可以用树链剖分求出

如上方那张图

如果我们要求$(a,b)$的$lca$,伪代码是这样的:

while top[a]!=top[b]//重链顶不同
    if a的深度<b的深度
        swap(a,b)
    a=top[a]的父亲//爬到下一条重链上
   
if a的深度>b的深度
    swap(a,b)
    
return a//当在同一条重链上时,较浅的即为其lca

这样就运用了树链剖分的特性来求$lca$,最坏时间复杂度为$O(log^2n)$

于是就基本完成啦!

最后是本题代码:
code:

#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define maxn 200001
int seg[maxn],in[maxn],out[maxn],dep[maxn],fa[maxn],top[maxn],son[maxn],siz[maxn];
int head[maxn],sum[maxn<<2],addv[maxn<<2],a[maxn];
int begins[maxn],endsss[maxn],suma[maxn];
struct edge
{
    int next,to;
}e[maxn<<1];
int tot=0;
void add(int u,int v)
{
    tot++;
    e[tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;
}
void dfs1(int u)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u])
        {
            continue;
        }
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
        {
            son[u]=v;
        }
    }
}
void dfs2(int u,int tp)
{
    tot++;
    in[u]=tot;
    seg[tot]=u;
    top[u]=tp;
    if(son[u])
    {
        dfs2(son[u],tp);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u]||v==son[u])
        {
            continue;
        }
        dfs2(v,v);
    }
    out[u]=tot;
}
int n,m,r;
#define pushup(o) sum[o]=sum[o<<1]^sum[o<<1|1]
void build(int o,int lf,int rg)
{
    if(lf==rg)
    {
        sum[o]=a[seg[lf]];
        return ;
    }
    int mid=(lf+rg)>>1;
    build(o<<1,lf,mid);
    build(o<<1|1,mid+1,rg);
    pushup(o);
}
int query(int o,int lf,int rg,int l,int r)
{
    if(l<=lf&&rg<=r)
    {
        return sum[o];
    }
    int ans=0;
    int mid=(lf+rg)>>1;
    if(l<=mid)
    {
        ans=ans^query(o<<1,lf,mid,l,r);
    }
    if(mid<r)
    {
        ans=ans^query(o<<1|1,mid+1,rg,l,r);
    }
    return ans;
}
int qpath(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        {
            swap(x,y);
        }
        ans=ans^query(1,1,n,in[top[x]],in[x]);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    ans=ans^query(1,1,n,in[y],in[x]);
    return ans;
}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
        {
            swap(u,v);
        }
        u=fa[top[u]];
    } 
    if(dep[u]>dep[v])
    {
        swap(u,v);
    }
    return u;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&begins[i],&endsss[i],&suma[i]);
        add(begins[i],endsss[i]);
        add(endsss[i],begins[i]);
    }
    tot=0;
    dep[1]=1;
    dfs1(1);
    tot=0;
    dfs2(1,1);
    for(int i=1;i<n;i++)
    {
        if(dep[begins[i]]>=dep[endsss[i]])
        {
            swap(begins[i],endsss[i]);
        }
        a[endsss[i]]=suma[i];//给深度较大的点赋边权
    }
    build(1,1,n);
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",qpath(x,y)^a[lca(x,y)]);
    }
}

chevron_left 洛谷P3943 星空

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名