P6072 『MdOI R1』Path

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=3e4+10;
int n,fir[N],nxt[N<<1],son[N<<1],w[N<<1],tot,F[N],Mx=-1,idx,idy,vis[N],G[N],P[N],dfn[N],bk[N],cnt,sz[N],Ans,in[N],out[N];
I void Add(CI x,CI y,CI z){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z;}
#define to son[i]
I void DFS(CI x,CI fa){RI i;for(i=fir[x];i;i=nxt[i]) to^fa&&(F[to]=F[x]^w[i],DFS(to,x),0);}
#define PA pair<int,int>
#define MP make_pair
class Trie{
    private:
        int ch[N*31][2],id[N*31],cnt;
    public:
        I void C(){RI i;for(i=0;i<=cnt;i++) ch[i][0]=ch[i][1]=id[i]=0;cnt=0;}
        I void U(CI x,CI dd){RI i,u=0;for(i=30;~i;i--) ch[u][x>>i&1]?u=ch[u][x>>i&1]:u=ch[u][x>>i&1]=++cnt;id[u]=dd;}
        I PA Q(CI x){RI i,u=0,X=0;for(i=30;~i;i--) ch[u][x>>i&1^1]?u=ch[u][x>>i&1^1],X=1<<i:u=ch[u][x>>i&1];return MP(X,id[u]);}
}T;//Trie 树维护异或和最大值
I void dfs(CI x,CI fa){RI i;for(P[x]=fa,bk[dfn[x]=++cnt]=x,sz[x]=1,i=fir[x];i;i=nxt[i]) to^fa&&(F[to]=F[x]^w[i],dfs(to,x),sz[x]+=sz[to],0);}
I void GT(CI x){RI i,j;PA t;for(i=fir[x];i;i=nxt[i]) if(!vis[to]){for(j=dfn[to];j<=dfn[to]+sz[to]-1;j++) t=T.Q(F[bk[j]]),Ans=max(Ans,Mx+t.first),T.U(F[bk[j]],bk[j]);T.C();}}//分界点不在链上，求与链相邻子树答案
I void FG(CI x){RI i,j;PA t;for(t=T.Q(F[x]),in[x]=max(in[x],t.first),T.U(F[x],x),i=fir[x];i;i=nxt[i]) if(!vis[to]) for(j=dfn[to];j<=dfn[to]+sz[to]-1;j++) t=T.Q(F[bk[j]]),in[x]=max(in[x],t.first),T.U(F[bk[j]],bk[j]);}//分界点在链上，求子树内答案
I void FO(CI x){RI i,j;PA t;for(t=T.Q(F[x]),out[x]=max(out[x],t.first),T.U(F[x],x),i=fir[x];i;i=nxt[i]) if(!vis[to]) for(j=dfn[to];j<=dfn[to]+sz[to]-1;j++) t=T.Q(F[bk[j]]),out[x]=max(out[x],t.first),T.U(F[bk[j]],bk[j]);}//分界点在链上，求子树外答案
int main(){
    RI i,x,y,z,lst;PA t;for(read(n),i=1;i<n;i++) read(x,y,z),Add(x,y,z),Add(y,x,z);for(DFS(1,0),i=1;i<=n;i++) t=T.Q(F[i]),Mx<t.first&&(Mx=t.first,idx=t.second,idy=i),T.U(F[i],i);//先求出全局异或和最大点对
    for(F[idx]=0,dfs(idx,0),vis[idx]=1,i=idy;i!=idx;i=P[i]) vis[i]=1;for(T.C(),GT(idx),i=idy;i!=idx;i=P[i]) GT(i);for(i=idy;i!=idx;i=P[i]) FG(i);FG(idx),T.C();//分界点不在链上
    for(F[idy]=cnt=0,dfs(idy,0),i=idx;i!=idy;i=P[i]) FO(i);FO(idy);for(lst=0,i=P[idx];i!=idy;i=P[i]) Ans=max(Ans,in[i]+lst),lst=max(lst,out[i]);//分界点在链上合并子树内子树外
    return Ans=max(Ans,in[idy]+lst),writeln(Ans),0;
}