P6072 『MdOI R1』Path

(Updated: )
oi

题目链接：P6072

给定一棵 $n$ 个节点的无根树，从中选择两个不交路径，求边权异或和之和最大值。

$n\leq 3\times 10^4$。

Sol

这里具体讲讲一只 $\log$ 的做法（在此感谢 神仙lwy）。

考虑这种题首先套路地枚举分界点 $x$，使两条路径一条在节点 $x$ 的子树内，另一条在子树外。

然后就很自然地想到了 $\mathcal O(n\log n\log w)$ 的 DSU+Trie 的做法处理子树内的部分，子树外的部分可以先利用 Trie 求出任意一对全局的异或和最大的点对 $(X,Y)$，那么显然所有不在 $X$ 到根和 $Y$ 到根的路径上的点的子树外的答案都是 $(X,Y)$ 间的异或和。考虑 $X$ 到根以及 $Y$ 到根的路径就直接从根节点出发，每次将点插入 Trie 中，维护出异或值最大即可，由于每个点只会被插一次，所以总复杂度为 $\mathcal O(n\log w)$。

然后考虑如何做到完全的一只 $\log$。还是先求出全局的异或和最大的 $(X,Y)$，然后把这条 $X$ 到 $Y$ 的链提取出来。

  • 如果分界点不在这条链上，显然子树外的答案取这个链的答案最优，子树内的答案直接求解与这条链相邻的子树内的答案即可，显然如果子树内的最优答案必然包含在与这条链相邻的子树内，这样每个点只会被插一次。
  • 如果分界点在这条链上，考虑先钦定 $X$ 为根，从 $Y$ 向上扫一遍，不断插入点，求出其异或和最大值即为当前点的子树内答案。类似的，钦定 $Y$ 为根，从 $X$ 向上扫一遍，不断插点，同样也能求出其子树外的答案。

由于每个点只会被插一次，所以这样的话总时间复杂度为 $\mathcal O(n\log w)$。

有一点点小细节，写的时候注意一下就好了。然后就跑的比两只 $\log$ 还慢。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}