P4551 最长异或路径 题解

· · 题解

本篇题解思路来源于《算法竞赛进阶指南》。

前置知识：

  1. 字典树
  2. 异或性质
  3. 最近公共祖先

有了以上知识的基础，我们才能高效地解决本道题目。若对以上知识点不熟悉，建议先做题巩固，再来尝试此题，会更有收获。下面的内容建立在熟悉以上知识点的基础上，不再对一些名词进行解释。

题目中要求我们寻找一条从树上 X 到 Y 的路径，使得他们路径上的所有边权异或起来的值最大。

整个问题不好直接入手,所以我们将其划分为两个子任务:

A. 求出两个结点间的边权异或和

B. 找到两个结点,使他们路径上的的边权异或和最大

如果我们熟悉异或性质，我们自然会想到：

A $ $xor$ $A$ $=$ $0

即，若两个相同的数异或，那么他们的值为0。 由于异或运算具有交换律与结合律的性质，那么：

对于 A xor B xor A

=$ $(A$ $xor$ $A)$ $xor$ $B =$ $0$ $xor$ $B =$ $B

因此,我们令 LCA 代表 X 与 Y 的最近公共祖先,令 Root 表示整颗树的根节点,令 Sum(X,Y) 表示从 X 到 Y 路径上所有边权的异或和,有:

Sum(X,Y) =$ $Sum(X,LCA)$ $xor$ $Sum(Y,LCA) =$ $Sum(X,LCA)$ $xor$ $Sum(Y,LCA)$ $xor$ $Sum(LCA,Root)$ $xor$ $Sum(LCA,Root) =$ $Sum(X,LCA)$ $xor$ $Sum(LCA,Root)$ $xor$ $Sum(Y,LCA)$ $xor$ $Sum(LCA,Root) =$ $Sum(X,Root)$ $xor$ $Sum(Y,Root)

因此,对于Sum(X,Y),我们并不需要知道他们之间的路径信息,我们只需要分别知道他们到根节点路径上的异或和即可。而这个操作是可以通过dfs O(n)实现的,具体实现细节在代码中。

此时，我们已经解决了一个子问题：如何快速求出两个结点间的边权异或和。令 Dis[X] 表示从 X 到根节点的边权异或和,那我们的任务就是找出一对(X,Y),

使得: Dis(X) xor Dis(Y) 最大。

现在我们来讨论，如何找到最大值，即最大异或对。我们可以扫描一遍 Dis数组 ,对每一个 Dis[X] ,尝试找到一个 Dis[Y] ,使 Dis[X] xor Dis[Y] 最大。明显有一种朴素的 O(n^2) 的算法,找出所有的 (X,Y) , 找出Dis[X] xor Dis[Y] 的最大值。但很明显，此时间复杂度会导致超时。

这个时候，我们需要使用一种数据结构——字典树。字典树是解决异或问题的有力数据结构，我们运用贪心的思想，可以很快地解决本题的第二个子任务。假设某棵树有4个结点，每个结点的 Dis 分别为:

Dis[1] = 0 Dis[2] = 6 Dis[3] = 3 Dis[4] = 5

这里不给出树的结构,因为当我们已经求出 Dis 数组后,树的结构已经无关紧要了,我们的第二个子任务与其没有关联。此时我们将每个 Dis[X] 的值视为一个二进制数,与插入字符串类似,将此数的二进制表示视作一个 01字符串 , 由二进制的高位到低位依次插入（在实际上，我们应该更高位，例如从31位开始插入，这里为了方便，从第2位开始插入（第0位为最低位））:

现在,我们已经在这棵线段树中插入了 Dis数组 的值。先抛出理论，令 Sum 表示异或和。在 Dis[X] 的二进制表示中，从高位到低位扫描，若 Dis[X] 当前位的值是 1 ,那么我们在当前字典树的子树中,从根节点向左儿子走(即向值为 0 的子节点走,在我的图中是左儿子)，并更新 Sum (具体在代码中);若没有左儿子,那我们只能向右走,不更新 Sum 。若当前位的值是 0 ,则相反，即每次向与当前位数值不同的节点走。这样的贪心策略是显然成立的。最后走到叶节点时，此时的 Sum 就是某个 Dis[Y] 与 Dis[X] 异或得到的最大值。

事实上,我们也可以得知 Dis[Y] 的值，在最后再令 Sum = Dis[X] xor Dis[Y] ，前面不更新 Sum 。想一想,怎么做?(提示:只用对 end 数组进行修改即可)。

下面是一个例子：寻找与 Dis[3] = 3 异或的最大值(答案为 Dis[4] = 5 )

至此,问题得到解决,剩下就是码代码了。下面是我的代码，仅供参考,时间复杂度应该近似于 O(n) ,但常数较大：

#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
#define N 100010

int n;
int head[N],nxt[N<<1],ver[N<<1],val[N<<1],tot=0;
int Dis[N];//此处Dis含义与上文相同
int trie[N<<4][2],cnt=1;//字典树
bool end[N<<4];//结束标识

inline void add(int x,int y,int z)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
    val[tot]=z;
}//邻接表存图

void dfs(int x,int fa)
{
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i],z=val[i];
        if(y == fa) 
            continue;   
        Dis[y]=(z^Dis[x]);
        dfs(y,x);
    }
    return ;
}//求出Dis数组

inline void insert(int x)
{
    int p=1;
    for(int i=31;i>=0;i--)
    {
        int num=((x>>i)&1);
        if(!trie[p][num])   
            trie[p][num]=++cnt;
        p=trie[p][num];
    }
    end[p]=1;
}//字典树-插入节点

inline int find(int num)
{
    int p=1;
    int Sum=0;
    for(int i=31;i>=0;i--)
    {
        int x=((num>>i)&1);
        if(trie[p][x^1])    
            Sum+=(1<<i),p=trie[p][x^1];//更新Sum
        else    
            p=trie[p][x];              //不更新Sum
    }
    return Sum;
}//字典树-求和

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    Dis[1]=0;
    dfs(1,0);

    for(int i=1;i<=n;i++)
        insert(Dis[i]);

    int Sum=0;
    for(int i=1;i<=n;i++)
        Sum=max(Sum,find(Dis[i]));
    printf("%d",Sum);
    return 0;
}