(luogu4551)最长异或路径

发表于 | 分类于 ， ，

原题链接

思路:

设从根到点$x$的路径异或和为$d_x$, 则从$x$到$y$的路径异或和是$d_x \oplus d_y$

原因很显然: 从根到$lca(x,y)$的路径异或和$d_{lca(x,y)}$同时会出现在$d_x$和$d_y$中, 两个异或之后就抵消了.

于是题目变成了找最大的两个值的异或的和. 显然使用01trie解决.

时间复杂度为$O(nloga)$, $a$表示值域上界.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdio>
#include <cctype>
const int Mn(100500),Mb(32);
template<typename T> void qrd(T& x) {
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x,Ts&... xs) { //快读
    qrd(x); qrd(xs...);
}

//建树
struct Edge {
    int e,w,nt;
}ed[Mn*2];
int vs[Mn];
void adde(int u,int v,int w) {
    static int ec(0);
    ed[++ec] = {v,w,vs[u]};
    vs[u] = ec;
}

//trie节点
struct Trd {
    int v;
    int zs, os;
}tr[Mn*35];
int rt; //根
int newTrd() {  //开辟节点
    static int tc(0);
    return ++tc;
}
void mdf(int& p,int bd,int mp) {    //修改
    if(p==0) {
        p = newTrd();
    }
    ++tr[p].v;
    if(bd==0) {
        return;
    }
    if(mp&(1<<(bd-1))) {
        mdf(tr[p].os,bd-1,mp);
    } else {
        mdf(tr[p].zs,bd-1,mp);
    }
}
int qry(int p,int bd,int qx) {      //查询最大异或值
    if(bd==0) {
        return 0;
    }
    if(qx&(1<<(bd-1))) {
        int mxz = tr[tr[p].zs].v;
        if(mxz>0) {
            return qry(tr[p].zs,bd-1,qx) | (1<<(bd-1));
        } else {
            return qry(tr[p].os,bd-1,qx);
        }
    } else {
        int mxz = tr[tr[p].os].v;
        if(mxz>0) {
            return qry(tr[p].os,bd-1,qx) | (1<<(bd-1));
        } else {
            return qry(tr[p].zs,bd-1,qx);
        }
    }
}
int dx[Mn]; //d_x
void dfs(int p, int f) {    //dfs预处理dx
    mdf(rt,Mb,dx[p]);
    for(int i(vs[p]);i;i=ed[i].nt) {
        Edge e(ed[i]);
        if(e.e!=f) {
            dx[e.e] = dx[p] ^ e.w;
            dfs(e.e,p);
        }
    }
}

int main() {
    int n; qrd(n);
    for(int i(1);i<n;++i) {
        int u,v,w;
        qrd(u,v,w);
        adde(u,v,w); adde(v,u,w);
    }
    dfs(1,0);
    int ans(0);
    for(int i(1);i<=n;++i) {    //寻找最大值
        int tmp = qry(rt,Mb,dx[i]);
        ans = tmp>ans ? tmp : ans;
    }
    printf("%d",ans);
    return 0;
}