最大Xor路径 | 解题报告

编程 解题报告

Description
求出这棵带边权的树的一条最大Xor路径
Input
第一行，一个整数N，表示一颗树有N个节点，接下来N-1行，每行三个整数a,b,c表示节点a和节点b之间有条权值为c的边(2<=n<=100000,1< a,b <=N,C<=2^31-1)
Output
输出仅一行，即所求的带边权树的Xor最大路径。

样例输入
4
1 2 3
1 3 4
1 4 7
样例输出
7

算法1 - 暴力的DFS

使用1遍DFS遍历可以扫描出n个节点到root（根节点）的XOR路径,时间复杂度为 O(n)；那么我们可以通过n遍DFS扫描出所有节点到所有其他节点的XOR路径，从而求得最大值。综合下来，时间复杂度为O(n^2)。妥妥超时~~~

算法2 - 一个“无用”的优化

我们来观察一下算法1，对于这个O(n^2)的算法，我们肯定不能去优化DFS的一层，也就是说，我们只能在枚举n个节点的一层下手，能不能只进行1遍DFS呢？答案是肯定的。
假设有这样1棵树：

6
1 2 a
2 3 b
3 4 c
4 5 d
1 6 e

我们用d[i]记录i节点到1节点的XOR距离，那么
d[3]=a xor b
d[5]=a xor c xor d
而3->5的XOR距离为 b xor c xor d = d[3] xor d[5]
于是我们得到 对于任意两点i,j(i<>j)，i到j的XOR距离为 d[i] xor d[j] (d[i]记录i节点到1节点的XOR距离)；
那么原题就转化为 在d[1..n]中，找出一对i,j(i<>j)，使d[i] xor d[j]最大。如果用暴力枚举的方法，时间复杂度仍然是 O(n^2)。

算法3 - 终极版优化

看上去我们已经不知道如何优化了，不如举几个例子。
98=(1100010)B
43=(101011)B
98 XOR 43 = (1001001)B = 73

算法2中，枚举i是必不可少的，所以我们只能在j上下功夫，要优化j，只能、必须做到精确查找对于D[i]最优的j。

代码(Pascal)

一遍AC！！！

    var
    head,d:array[0..100005] of longint;
    vet,val,next:array[0..200005] of longint;
    trie:array[0..3100005,0..2] of longint;
    edgenum,n,i,x,y,z,loc,ans,root,nodenum:longint;
function max(a,b:longint):longint;
begin
    if a>b then exit(a);
    exit(b);
end;
procedure addedge(u,v,cost:longint);
begin
    inc(edgenum);
    vet[edgenum]:=v;
    val[edgenum]:=cost;
    next[edgenum]:=head[u];
    head[u]:=edgenum;
end;
procedure dfs(u,fa:longint);
var
    e,v,cost:longint;
begin
    e:=head[u];
    while e<>0 do 
    begin
        v:=vet[e];
        cost:=val[e];
        if v<>fa then 
        begin
            d[v]:=d[u] xor cost;
            dfs(v,u);
        end;
        e:=next[e];
    end;
end;
procedure ins(root,val,id:longint);
var
    now,son,i:longint;
begin
    now:=root;
    for i:=30 downto 0 do 
    begin
        son:=val shr i and 1;
        if trie[now,son]=0 then 
        begin
            inc(nodenum);
            trie[now,son]:=nodenum;
        end;
        now:=trie[now,son];
    end;
    trie[now,2]:=id;
end;
function find_trie(root,key:longint):longint;
var now,son,i:longint;
begin
    now:=root;
    for i:=30 downto 0 do 
    begin
        son:=key shr i and 1;
        if trie[now,son xor 1]<>0 then now:=trie[now,son xor 1]
        else now:=trie[now,son];
    end;
    exit(trie[now,2]);
end;
begin
    readln(n);
    edgenum:=0;
    for i:=1 to n-1 do 
    begin
        readln(x,y,z);
        addedge(x,y,z);
        addedge(y,x,z);
    end;
    dfs(1,-1);
    root:=1; nodenum:=1;
    for i:=1 to n do 
        ins(root,d[i],i);
    ans:=d[1] xor d[2];
    for i:=1 to n do 
    begin
        loc:=find_trie(root,d[i]);
        ans:=max(ans,d[i] xor d[loc]);
    end;
    writeln(ans);
end.

算法链接

Trie树（字典树）