你说得对，但是考虑分块

heaksicn · 2024-01-10 10:30:20 · 题解

给出一个不使用回滚莫队的纯分块做法。

首先考虑枚举一个点对 (x,y) 的 lca，记为 L，如果另一个点对 (u,v) 都不在都不在 l 的子树内，那么 E(x,y) 和 E(u,v) 一定不交。

那么题目就变成如何求在一棵子树内和外分别取出一对点，使得两个点的路径的异或和最大。

将树通过 dfn 序拍到一个序列上，L 的子树就变成了一个区间 [l_L,r_L]。那么问题就变成了：

• 求出区间 [l,r] 的两个点，他们的异或和最大。

• 求出区间 [1,l-1] \cup [r+1,n] 的两个点，他们的异或和最大。

转换到这里，我们考虑分块。令每一块的块长为 B。

对于每一个块 j，将块内的点全部压进 0-1 trie 里面。再对于每个点 i，求出它与块内所有点匹配的最大异或和，记为 g_{i,j}。

在这个基础上，可以求出在块 i 和块 j 中分别取出一个点的最大异或和,记为 f_{i,j}。

这部分的复杂度为 O(nB\log V)，其中 V 是值域。

以询问的前一部分为例：

• 对于两个散块中的点匹配的答案，同样可以将这些点压进 0-1 trie 里面求。时间复杂度为 O(B\log V)。

• 对于一个散块中的点和和整块中的点匹配的答案，可以将 g 压进线段树里面求出。时间复杂度为 O(B\log \frac{n}{B})。

• 对于两个整块中的点匹配的答案，同样可以将 f 放到线段树里面求出。时间复杂度为 O(\frac{n}{B}\log \frac{n}{B})。

询问的第二部分同理。

所以询问总的复杂度为 O(n(B\log V+B\log \frac{n}{B}+\frac{n}{B}\log \frac{n}{B}))。

取 B=\sqrt n 即可通过本题。

code

//Man always remember love because of romance only!
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
struct edge{
    int to,nxt,w;
}e[60001];
int head[30001],cnt;
void add(int u,int v,int w){
    cnt++;
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int dfn[30001],tot,a[30001],mx[30001],dep[30001];
void dfs(int x,int fa){
    dfn[x]=++tot;
    a[dfn[x]]=dep[x];
    mx[x]=dfn[x];
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dep[v]=dep[x]^e[i].w;
        dfs(v,x);
        mx[x]=max(mx[x],mx[v]);
    }
}
int n,B;
int id[30001];
int f[201][201],g[30001][201];
int tr[30001][2],nw;
int fl[30001];
void insert(int x){
    int now=0;
    for(int i=30;i>=0;i--){
//      cout<<now<<" ";
        int tp=((x>>i)&1);
        if(!tr[now][tp]) tr[now][tp]=++nw;
        now=tr[now][tp];
    }
    fl[now]=x;
//  cout<<now<<" "<<x<<endl;
//  puts("");
}
int query(int x){
    if(nw==0) return x;
    int now=0,res=0;
    for(int i=30;i>=0;i--){
//      cout<<now<<" ";
        int tp=((x>>i)&1);
        if(tr[now][tp^1]!=0){
            now=tr[now][tp^1];
        }else{
            now=tr[now][tp];
        }
    }
//  cout<<now<<" "<<fl[now]<<endl;
    return fl[now];
}
int trg[30001][801];
void pushup(int x,int id){
    trg[id][x]=max(trg[id][x<<1],trg[id][x<<1|1]);
}
void build(int x,int l,int r,int id){
    if(l==r){
        trg[id][x]=g[id][l];
        return;
    }
    int mid=(l+r)/2;
    build(x<<1,l,mid,id);
    build(x<<1|1,mid+1,r,id);
    pushup(x,id);
}
int query(int x,int l,int r,int nl,int nr,int id){
    if(nl>nr) return 0;
    if(nl<=l&&nr>=r) return trg[id][x];
    int res=0,mid=(l+r)/2;
    if(mid>=nl) res=max(res,query(x<<1,l,mid,nl,nr,id));
    if(mid<nr) res=max(res,query(x<<1|1,mid+1,r,nl,nr,id));
    return res;
}
int trf[201][801];
void pushup2(int x,int id){
    trf[id][x]=max(trf[id][x<<1],trf[id][x<<1|1]);
}
void build2(int x,int l,int r,int id){
    if(l==r){
        trf[id][x]=f[id][l];
        return;
    }
    int mid=(l+r)/2;
    build2(x<<1,l,mid,id);
    build2(x<<1|1,mid+1,r,id);
    pushup2(x,id);
}
int query2(int x,int l,int r,int nl,int nr,int id){
    if(nl>nr) return 0;
    if(nl<=l&&nr>=r) return trf[id][x];
    int res=0,mid=(l+r)/2;
    if(mid>=nl) res=max(res,query2(x<<1,l,mid,nl,nr,id));
    if(mid<nr) res=max(res,query2(x<<1|1,mid+1,r,nl,nr,id));
    return res;
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
//  cout<<"complete cin\n";
    B=sqrt(n);
    for(int i=1;i<=n;i++) id[i]=(i-1)/B+1;
//  for(int i=1;i<=n;i++) cout<<dfn[i]<<" ";
//  puts("");
//  for(int i=1;i<=n;i++) cout<<a[i]<<" ";
//  cout<<endl;
//  for(int i=1;i<=n;i++) cout<<id[i]<<" ";
//  cout<<endl;
    for(int i=1;i<=id[n];i++){
//      cout<<"i="<<i<<endl;
        for(int j=0;j<=nw;j++) tr[j][0]=tr[j][1]=0,fl[j]=0; 
        nw=0;
//      cout<<"l="<<(i-1)*B+1<<",r="<<min(i*B,n)<<endl;
        for(int j=(i-1)*B+1;j<=min(i*B,n);j++) insert(a[j]);
        for(int j=1;j<=n;j++){
//          if(id[j]==i) continue;
            g[j][i]=a[j]^query(a[j]);
            f[id[j]][i]=max(f[id[j]][i],g[j][i]);
        }
    }
//  for(int i=1;i<=n;i++){
//      for(int j=1;j<=id[n];j++) cout<<g[i][j]<<" ";
//      puts("");
//  }
//  cout<<"complete init\n";
    for(int i=1;i<=n;i++) build(1,1,id[n],i);
    for(int i=1;i<=id[n];i++) build2(1,1,id[n],i);
//  cout<<"complete building segment-tree\n";
    int ans=0;
    for(int x=1;x<=n;x++){
        int l=dfn[x],r=mx[x];
//      cout<<"l="<<l<<",r="<<r<<endl;
        for(int j=0;j<=nw;j++) tr[j][0]=tr[j][1]=0; 
        nw=0;
        int res=0;
        if(id[l]==id[r]){
            for(int i=l;i<=r;i++){
                insert(a[i]);
                res=max(res,a[i]^query(a[i]));
            }
        }else{
            for(int i=l;i<=id[l]*B;i++){
                insert(a[i]);
                res=max(res,a[i]^query(a[i]));
            }
            for(int i=(id[r]-1)*B+1;i<=r;i++){
                insert(a[i]);
                res=max(res,a[i]^query(a[i]));
            }
            int nl=id[l]+1,nr=id[r]-1;
            for(int i=l;i<=id[l]*B;i++) res=max(res,query(1,1,id[n],nl,nr,i));
            for(int i=(id[r]-1)*B+1;i<=r;i++) res=max(res,query(1,1,id[n],nl,nr,i));
            for(int i=nl;i<=nr;i++) res=max(res,query2(1,1,id[n],i+1,nr,i));
        }
        int res2=0;
        r=dfn[x]-1,l=mx[x]+1;
        for(int j=0;j<=nw;j++) tr[j][0]=tr[j][1]=0,fl[j]=0; 
        nw=0;
        int nl=id[l]+1,nr=id[r]-1;
        if(r<=0&&l>n){
            res2=-2e9;
        }else if(r<=0&&l<=n){
            for(int i=l;i<=min(id[l]*B,n);i++){
                insert(a[i]);
                res2=max(res2,a[i]^query(a[i]));
            }
            for(int i=l;i<=min(id[l]*B,n);i++) res2=max(res2,query(1,1,id[n],nl,id[n],i));
            for(int i=nl;i<=id[n];i++) res2=max(res2,query2(1,1,id[n],nl,id[n],i));
        }else if(r>0&&l>n){
            for(int i=(id[r]-1)*B+1;i<=r;i++){
                insert(a[i]); 
                res2=max(res2,a[i]^query(a[i]));
            }
            for(int i=(id[r]-1)*B+1;i<=r;i++) res2=max(res2,query(1,1,id[n],1,nr,i));
            for(int i=1;i<=nr;i++) res2=max(res2,query2(1,1,id[n],1,nr,i));
        }else{
            for(int i=l;i<=min(id[l]*B,n);i++){
                insert(a[i]);
                res2=max(res2,a[i]^query(a[i]));
            }
            for(int i=(id[r]-1)*B+1;i<=r;i++){
                insert(a[i]); 
                res2=max(res2,a[i]^query(a[i]));
            }
            for(int i=l;i<=min(id[l]*B,n);i++) res2=max(res2,max(query(1,1,id[n],1,nr,i),query(1,1,id[n],nl,id[n],i)));
            for(int i=(id[r]-1)*B+1;i<=r;i++) res2=max(res2,max(query(1,1,id[n],1,nr,i),query(1,1,id[n],nl,id[n],i)));
            for(int i=1;i<=nr;i++) res2=max(res2,max(query2(1,1,id[n],nl,id[n],i),query2(1,1,id[n],1,nr,i)));
            for(int i=nl;i<=id[n];i++) res2=max(res2,max(query2(1,1,id[n],1,nr,i),query2(1,1,id[n],nl,id[n],i)));
        }   
//      cout<<res<<" "<<res2<<endl;
        ans=max(ans,res+res2);
    }
    write(ans);
    return 0;
}