题解 bzoj1954【Pku3764 The xor

题解 bzoj1954【Pku3764 The xor – longest Path】

做该题之前，至少要先会做这道题。

记 (d[u]) 表示 (1) 到 (u) 简单路径的异或和，该数组可以通过一次遍历求得。

(~)

考虑 (u) 到 (v) 简单路径的异或和该怎么求？

令 (z=operatorname{lca}(u,v)) ，则 (u) 到 (v) 简单路径的异或和可以分成两段求解：一段是 (z) 到 (u) 简单路径的异或和，一段是 (z) 到 (v) 简单路径的异或和，二者异或一下即为 (u) 到 (v) 简单路径的异或和。

由于异或 "(a operatorname{xor} a=0)" 的性质，两条路径重叠的部分异或起来即为 (0)，可得

(z) 到 (v) 简单路径的异或和为

[d[u] operatorname{xor} d[z] ]

(z) 到 (v) 简单路径的异或和为

[d[v] operatorname{xor} d[z] ]

进一步，可得

(u) 到 (v) 简单路径的异或和为

[(d[u]operatorname{xor}d[z])operatorname{xor}(d[v]operatorname{xor}d[z]) ]

由于异或满足交换律，可化简为

[d[u]operatorname{xor}d[v] ]

由上述性质，答案即为 (maxlimits_{1leq i<jleq n})({d[i] operatorname{xor} d[j]})，又回到了这道题，字典树直接解决即可。

时间复杂度 ( heta(32n)) 。

CODE

#include<cstdio>
#include<algorithm>
#include<queue>

#define RI register int

using namespace std;

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

const int N=100100,M=200100;

int n;
int tot_E,head[N],ver[M],edge[M],Next[M];

void add(int u,int v,int w)
{
    ver[++tot_E]=v;    edge[tot_E]=w;    Next[tot_E]=head[u];    head[u]=tot_E;
}

int d[N];
int vis[N];

void bfs()
{
    queue<int>q;
    q.push(1);vis[1]=1;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(RI i=head[u];i;i=Next[i])
        {
            int v=ver[i],w=edge[i];
            if(vis[v])continue;
            vis[v]=1;
            d[v]=d[u]^w;
            q.push(v);
        }
    }
} 

int trie[N*32+10][2],tot=1;
int ans;

void insert(int num)
{
    int p=1;
    for(RI k=31;k>=0;k--)
    {
        int ch=num>>k&1;
        if(trie[p][ch]==0)trie[p][ch]=++tot;
        p=trie[p][ch];
    }
}

int search(int num)
{
    int p=1,sum=0;
    for(RI k=31;k>=0;k--)
    {
        int ch=num>>k&1;
        if(trie[p][ch^1])p=trie[p][ch^1],sum+=1<<k;
        else p=trie[p][ch];
        if(p==0)return sum;
    }
    return sum;
}

int main()
{
    scanf("%d",&n);
    for(RI i=1;i<n;i++)
    {
        int u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);
    }

    bfs();

    for(RI i=1;i<=n;i++)
    {
        ans=max(ans,search(d[i]));
        insert(d[i]);
    }

    printf("%d
",ans);

    return 0;
}

题解 bzoj1954【Pku3764 The xor – longest Path】

CODE

thanks for watching