最长异或路径

Posted on Edited on In Word count in article: 468 Reading time ≈ 2 mins.
最长异或路径

The XOR-longest Path

题目大意

给定一棵树, 让你求树上异或和最大的简单路径的异或和

分析

想要异或和最大, 那么我们想要的显然是贪心, 那就是尽量让他们在二进制下不相同

这样考虑的话, 我们可以想到的是\(01\)字典树, 从高次项向低处贪心, 能保证最值

那么还有一个问题, 如何求一个简单路径的异或值?

我们又可以想到关于异或的优良性质:\(x\otimes y\otimes x=y\)

就是说, 可以随机找一个根, 求\(root\)到其他所有结点的链的路径异或和

如果我们要求的是\(sum_{i,j}\), 那么它就可以十分简单的表示为\(sum_{root,i}\otimes sum_{root,j}\)

那么我们把所有的从根开始的路径插入到\(01\)字典树中, 暴力查询跟新答案就好惹

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
#include <cstdio>

const int Maxn = 100000 + 5;
int Tree[Maxn * 31][2], Id;
int Xor[Maxn];
int N, U, V, C, Ans;
int Head[Maxn], Next[Maxn << 1], Edge[Maxn << 1], W[Maxn << 1], Cur;

inline void AddEdge(int U, int V, int C)
{
    Next[++Cur] = Head[U];
    Head[U] = Cur;
    Edge[Cur] = V;
    W[Cur] = C;
}

inline void Insert(int X, int Rt = 0)
{
    for (int i = 1 << 30; i; i >>= 1)
    {
        bool F = X & i;
        if (!Tree[Rt][F]) Tree[Rt][F] = ++Id;
        Rt = Tree[Rt][F];
    }
}

inline int Query(int X, int Rt = 0, int Ans = 0)
{
    for (int i = 1 << 30; i; i >>= 1)
    {
        bool F = X & i;
        if (Tree[Rt][!F]) Ans += i, Rt = Tree[Rt][!F];
        else Rt = Tree[Rt][F];
    }
    return Ans;
}

void DFS(int U, int F)
{
    for (int i = Head[U]; i; i = Next[i])
    {
        if (Edge[i] == F) continue;
        Xor[Edge[i]] = Xor[U] ^ W[i];
        DFS(Edge[i], U);
    }
}

inline int max(int a, int b){return a > b ? a : b;}

int main()
{
    scanf("%d", &N);
    for (int i = 1; i < N; ++i)
    {
        scanf("%d %d %d", &U, &V, &C);
        AddEdge(U, V, C), AddEdge(V, U, C);
    }
    DFS(1, 1);
    for (int i = 1; i <= N; ++i) Insert(Xor[i]);
    for (int i = 1; i <= N; ++i) Ans = max(Ans, Query(Xor[i]));
    printf("%d\n", Ans);
}