P6072 『MdOI R1』Path
题目链接：P6072
给定一棵 n 个节点的无根树，从中选择两个不交路径，求边权异或和之和最大值。
nleq 3times 10^4。
Sol
这里具体讲讲一只 log 的做法（在此感谢 神仙lwy）。
考虑这种题首先套路地枚举分界点 x，使两条路径一条在节点 x 的子树内，另一条在子树外。
然后就很自然地想到了 mathcal O(nlog nlog w) 的 DSU Trie 的做法处理子树内的部分，子树外的部分可以先利用 Trie 求出任意一对全局的异或和最大的点对 (X,Y)，那么显然所有不在 X 到根和 Y 到根的路径上的点的子树外的答案都是 (X,Y) 间的异或和。考虑 X 到根以及 Y 到根的路径就直接从根节点出发，每次将点插入 Trie 中，维护出异或值最大即可，由于每个点只会被插一次，所以总复杂度为 mathcal O(nlog w)。
然后考虑如何做到完全的一只 log。还是先求出全局的异或和最大的 (X,Y)，然后把这条 X 到 Y 的链提取出来。
- 如果分界点不在这条链上，显然子树外的答案取这个链的答案最优，子树内的答案直接求解与这条链相邻的子树内的答案即可，显然如果子树内的最优答案必然包含在与这条链相邻的子树内，这样每个点只会被插一次。
- 如果分界点在这条链上，考虑先钦定 X 为根，从 Y 向上扫一遍，不断插入点，求出其异或和最大值即为当前点的子树内答案。类似的，钦定 Y 为根，从 X 向上扫一遍，不断插点，同样也能求出其子树外的答案。
由于每个点只会被插一次，所以这样的话总时间复杂度为 mathcal O(nlog w)。
有一点点小细节，写的时候注意一下就好了。然后就跑的比两只 log 还慢。。。
代码语言：javascript复制#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 '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;
}
