Love Live!-01字典树启发式合并

链接：https://ac.nowcoder.com/acm/contest/201/D?&headNav=www

思路：题目要求的是每个等级下的最大简单路径中的最大异或值，那么我们为了保证目前的路径中最大的权值

为当前访问的边，先进行排序，然后一条一条的插入边，并查集维护各个联通块，启发式合并，由当前边连接起来的

两个联通块，所谓启发式合并也就是把小的块合并到大的上。然后查询的时候就是再当前这条边的两个联通块中

找一个包含此边的最大异或路径，为了方便处理我们可以把每个点存储一个到它并查集根节点的异或值，

这样进行 0 1 字典树维护即可。

#include<bits/stdc++.h>

using namespace std;

#define maxn 234567

vector<int>gra[maxn];

int tree[maxn*100][3],ans[maxn];

int n,m,u,v,w,root[maxn],tx,ty;

int fa[maxn],val[maxn],tot,sz[maxn];

struct node

{

    int x,y,w;

    bool operator<(const node &b)const

    {

        return w<b.w;

    }

} edge[maxn];

int fond(int x)

{

    return x==fa[x]?x:fa[x]=fond(fa[x]);

}

void updata(int x,int ad)

{

    for(int i=20; i>=0; i--)

    {

        int id=((1<<i)&ad)?1:0;

        if(!tree[x][id])

            tree[x][id]=++tot;

        x=tree[x][id];

    }

}

int query(int x,int ad)

{

    int ret=0;

    for(int i=20; i>=0; i--)

    {

        int id=((1<<i)&ad)?1:0;

        if(tree[x][id^1])

        {

            x=tree[x][id^1];

            ret|=(1<<i);

        }

        else x=tree[x][id];

    }

    return ret;

}

int main()

{

    scanf("%d",&n);

    for(int i=1; i<n; i++)

    {

        scanf("%d%d%d",&u,&v,&w);

        edge[i]=(node{u,v,w});

    }

    sort(edge+1,edge+n);

    for(int i=1; i<=n; i++)

    {

        fa[i]=i;

        sz[i]=1;

        gra[i].push_back(i);

        root[i]=++tot;

        updata(root[i],0);

    }

    for(int i=1; i<n; i++)

    {

        u=edge[i].x,tx=fond(u);

        v=edge[i].y,ty=fond(v);

        w=(edge[i].w^val[u]^val[v]);

        if(sz[tx]>sz[ty])swap(tx,ty),swap(u,v);

        for(int j=0; j<sz[tx]; j++)

            ans[i]=max(ans[i],query(root[ty],(w^val[gra[tx][j]])));

        for(int j=0; j<sz[tx]; j++)

        {

            val[gra[tx][j]]^=w;

            gra[ty].push_back(gra[tx][j]);

            updata(root[ty],val[gra[tx][j]]);

        }

        fa[tx]=ty;

        sz[ty]+=sz[tx];

    }

    for(int i=1; i<n; i++)

    {

        printf("%d",ans[i]);

        if(i!=n-1)printf(" ");

        else printf("\n");

    }

    return 0;

}

巴特西

Love Live!-01字典树启发式合并

最新文章

热门文章