[LuoguP4551]最长异或路径

01Trie。但是我在建树的时候没有记录父亲指针，然后两个指针光往下跳没往回跳了emmmm太坑了！浪费爷好多时间emmm
总体思想是树上(u,v)异或路径等于从根节点到u的异或路径异或上从根节点到y的异或路径。因为一个数异或两次就等于没有异或。所以也不用求lca啦！

#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
struct Trie_Tree{
    Trie_Tree *so[2],*fa;
    int nu;
    Trie_Tree(){
        so[0]=so[1]=fa=NULL;
    }
    void add(int num,int pos){
        if(pos<0) {nu=num;return;}
        bool b=(1<<pos)#
        if(so[b]==NULL) (so[b]=new Trie_Tree)->add(num,pos-1);
                    else so[b]->add(num,pos-1);
        so[b]->fa=this;
    }
}*Ttr;
Trie_Tree *tmp1,*tmp2;
int ans[35],anss,sum;
void query(int pos){
    bool tag=false;
    if(pos<0){
        sum=0;
        for(int i=0;i<=30;++i)
            sum+=(1<<i)*ans[i];
        anss=max(anss,sum);
        return;
    }
    if(tmp1->so[1]!=NULL&&tmp2->so[0]!=NULL){
        tag=true;
        ans[pos]=1;
        tmp1=tmp1->so[1];
        tmp2=tmp2->so[0];
        query(pos-1);
        tmp1=tmp1->fa;
        tmp2=tmp2->fa;
        ans[pos]=0;
    }
    if(tmp1->so[0]!=NULL&&tmp2->so[1]!=NULL){
        tag=true;
        ans[pos]=1;
        tmp1=tmp1->so[0];
        tmp2=tmp2->so[1];
        query(pos-1);
        tmp1=tmp1->fa;
        tmp2=tmp2->fa;
        ans[pos]=0;
    }
    if(tag) return;
    if(tmp1->so[1]!=NULL&&tmp2->so[1]!=NULL){
        tmp1=tmp1->so[1];
        tmp2=tmp2->so[1];
        query(pos-1);
        tmp1=tmp1->fa;
        tmp2=tmp2->fa;
    }
    if(tmp1->so[0]!=NULL&&tmp2->so[0]!=NULL){
        tmp1=tmp1->so[0];
        tmp2=tmp2->so[0];
        query(pos-1);
        tmp1=tmp1->fa;
        tmp2=tmp2->fa;
    }
}
struct node{
    int to,wi;
    node*next;
}*con[maxn];
void addedge(int x,int y,int w){
    node*p=new node;
    p->to=y;p->wi=w;
    p->next=con[x];
    con[x]=p;
}
bool vis[maxn];
int f[maxn];
void dfs(int v){
    vis[v]=true;
    for(node*p=con[v];p;p=p->next)
    if(!vis[p->to]){
        f[p->to]=f[v]^p->wi;
        dfs(p->to);
    }
}
int n;
int main(){
    scanf("%d",&n);
    int x,y,w;
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&x,&y,&w);
        addedge(x,y,w);addedge(y,x,w);
    }
    dfs(1);
    Ttr=new Trie_Tree();
    int mx=0;
    for(int i=1;i<=n;++i)
        Ttr->add(f[i],30);
    tmp1=tmp2=Ttr;
    query(30);
    cout<<anss;
    return 0;
}