【Coel.学习笔记】【一个阶段的结束】01-Trie树（01字典树）求异或路径

本文主要是介绍【Coel.学习笔记】【一个阶段的结束】01-Trie树（01字典树）求异或路径，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题前闲语

是的，变成闲语了（别问我为什么要改）
今天考完了月考，虽然发挥得不是很好但终归是结束了，休息一下~
刚好深进也到货了，开始新一轮学习吧！

题目简介

题目描述

给定一棵 \(n\) 个点的带权树，结点下标从 \(1\) 开始到 \(n\)。寻找树中找两个结点，求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入输出格式

输入格式

第一行一个整数 \(n\)，表示点数。
接下来 \(n-1\) 行，给出 \(u,v,w\) ，分别表示树上的 \(u\) 点和 \(v\) 点有连边，边的权值是 \(w\)。

输出格式

一行，一个整数表示答案。

解题思路

考虑用链式前向星存图，求出每个节点到根节点（自行定义根节点为\(1\)）的异或路径，那么两个节点的异或路径就是它们与根节点路径的异或值。
先用\(dfs\)初始化每个节点的异或值：

struct edge {
    int next, to, w;
} edge[maxn];

int p[maxn], cnt;

void add_edge(int u, int v, int w) {
    edge[++cnt].next = p[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    p[u] = cnt;
}

void init(int x, int f) {//dfs
    for (int i = p[x]; i != 0; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        if (v != f) {
            s[v] = s[x] ^ w;
            init(v, x);
        }
    }
}

然后暴力枚举。当然直接暴力枚举的话复杂度是\(O(n^2)\)，没法通过\(n=10^5\)，所以需要用\(01-Trie\)优化。
（此处待补充）
代码如下：

#include <cctype>
#include <cstdio>
#include <iostream>
#include <vector>

namespace FastIO {
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    static int buf[35];
    int top = 0;
    do {
        buf[top++] = x % 10;
        x /= 10;
    } while (x);
    while (top)
        putchar(buf[--top] + '0');
    puts("");
}
}  // namespace FastIO

using namespace std;
using namespace FastIO;

const int maxn = 1e5 + 10;

struct edge {
    int next, to, w;
} edge[maxn];

int p[maxn];
int n, cnt, tot, ans;
int s[maxn], ch[maxn * 32][2];

void add_edge(int u, int v, int w) {
    edge[++cnt].next = p[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    p[u] = cnt;
}

void init(int x, int f) {
    for (int i = p[x]; i != 0; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        if (v != f) {
            s[v] = s[x] ^ w;
            init(v, x);
        }
    }
}

void insert(int v) {
    int u = 0;
    for (int i = (1 << 30); i; i >>= 1) {
        bool c = v & i;
        if (!ch[u][c])
            ch[u][c] = ++tot;
        u = ch[u][c];
    }
}

int find(int v) {
    int ans = 0, u = 0;
    for (int i = (1 << 30); i; i >>= 1) {
        bool c = v & i;
        if (ch[u][!c]) {
            ans += i;
            u = ch[u][!c];
        } else
            u = ch[u][c];
    }
    return ans;
}

int main() {
    n = read();
    for (int i = 1; i <= n - 1; i++) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    init(1, -1);
    for (int i = 1; i <= n; i++)
        insert(s[i]);
    for (int i = 1; i <= n; i++)
        ans = max(ans, find(s[i]));
    write(ans);
    return 0;
}

这篇关于【Coel.学习笔记】【一个阶段的结束】01-Trie树（01字典树）求异或路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！