【BZOJ】1954: Pku3764 The xor-longest Path

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【算法】trie树+xor路径

【题解】

套路1：统计从根到每个点的xor路径和，由于xor的自反性，两个点到根的xor路径和异或起来就得到两点间路径和。

然后问题就是找到n个值中异或值最大的两个值，考虑枚举每个数字，对于一个数找到与其异或和最大的数。

套路2：对所有数值二进制建01-trie，对于一个已知数字在trie上每一层尽量往另一端走，O(log n)得到与其异或和最大的数。

复杂度O(n log n)。

另一种做法，用两个指针从根往下，尽量分叉走，查询总复杂度O(log n)，但是建树仍然需要O(n log n)。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=;

struct edge{int v,w,from;}e[maxn*];

int t[maxn*][],dfsnum=,cnt=,tot=,p[maxn*],first[maxn],n;

bool val[maxn*];

void insert(int u,int v,int w)

{tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}

void push(int x){

    int u=;

    for(int i=;i>=;i--){

        bool c=x&(<<i);

        if(!t[u][c])t[u][c]=++dfsnum;

        u=t[u][c];

    }

    val[u]=;

}

int find(int x){

    int u=,ans=;

    for(int i=;i>=;i--){

        bool c=x&(<<i);

        if(!t[u][!c])u=t[u][c];

        else{u=t[u][!c];ans|=(<<i);}

    }

    return ans;

}

void dfs(int x,int fa,int num){

    push(p[++cnt]=num);

    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){

        dfs(e[i].v,x,num^e[i].w);

    }

}

int main(){

    scanf("%d",&n);

    int u,v,w;

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

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

        insert(u,v,w);

        insert(v,u,w);

    }

    dfs(,-,);

    int ans=;

    for(int i=;i<=cnt;i++){

        ans=max(ans,find(p[i]));

    }

    printf("%d",ans);

    return ;

}