【每日一题】9月17日题目精讲(01字典树）

利用异或的性质转化，再用字典树维护。首先我们知道树上两点必定有且只有一条简单路径，并且他们的关系有两种情况
1.他们具有祖孙关系，对于这种情况，我们记f[i]表示根节点到i的异或路径，那么f[i]xor f[j]即为i,j的异或路径
2.他们不具有祖孙关系，那么我们假如已知他们的LCA，根据第一种情况，所以异或路径值为(f[i]⨁f[lca])⨁(f[lca]⨁[j])，而异或操作满***换律和结合律，因此即为f[i]⨁f[j]。我们已经得出了树上两点间的异或路径的求法。只有处理出f数组，题目就相当于从f数组中选出两个数使它们的异或值最大，用字典树即可。

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
typedef long long ll;
#define INF 0x3f3f3f3f
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int maxn = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)        //快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
///////////////////////////////////////////////////////////
struct Edge
{
    int v, w, next;
}edge[maxn];
int head[maxn],t;
int ch[maxn][3], f[maxn];
inline void Add_edge(int u, int v, int w)
{
    edge[++t].next = head[u];
    head[u] = t;
    edge[t].v = v;
    edge[t].w = w;
}
void dfs(int u, int fa) {
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) {
            continue;
        }
        f[v] = f[u] ^ edge[i].w;//f数组存储着异或
        dfs(v, u);//接着遍历子节点
    }
}
void insert(int x)//01字典树插入模板
{
    int u=1;
    for(int i=1<<30;i;i>>=1)
    {
        int num=(x&i)?1:0;
        if(!ch[u][num])ch[u][num]=++t;
        u=ch[u][num];
    }
}
int find(int x)//01字典树查询模板
{
    int u=1,ans=0;
    for(int i=1<<30;i;i>>=1)
    {
        int num=(x&i)?0:1;
        if(ch[u][num])
        {
            u=ch[u][num];
            ans+=i;
        }
        else u=ch[u][!num];
    }
    return ans;
}
int main() {
    int n;
    cin >> n;
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        Add_edge(u, v, w);
        Add_edge(v, u, w);
    }
    dfs(1, 0);
    t = 1;
    for (int i = 1; i <= n; i++) {
        insert(f[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, find(f[i]));
    }
    cout << ans << endl;
    return 0;
}
/*
4
1 2 3
2 3 4
2 4 6
*/