POJ 3764 The xor-longest Path (01字典树)

题目大意：

给定一颗$n$个节点$(n\leq10^5)$，有边权的树，其边权$(0\leq w < 2^{31})$。让你求出这棵树上任意两个节点之间的异或最大值。

解题分析：

先用DFS预处理出根节点到所有节点的路径异或值，然后任意两点$u,v$之间的路径异或值就能通过 $(u->rt) xor (v->rt)$的异或值得到，因为根节点到u、v的最近公共祖先的路径被异或了两次，所以能够直接得到u,v之间的异或距离。但是因为节点数量有$10^5$个，直接枚举两两节点肯定超时。用01字典树优化一下，快速找到异或的最大值。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

typedef long long ll;

template<typename T>

inline void read(T&x){

  x=;int f=;char ch=getchar();

  while(ch<'' ||ch>''){ if(ch=='-')f=-; ch=getchar(); }

  while(ch>='' && ch<=''){ x=x*+ch-''; ch=getchar(); }

  x*=f;

}

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define clr(a,b) memset(a,b,sizeof(a))

const int N = 1e5+;

ll nxt[N*][],xoval[N];

int n,rt;

struct Edge{int to,nxt;ll w; }e[N<<];

int head[N],cnt,pos;

inline void init(){

  cnt=;clr(head,-);

  pos=;clr(nxt,);clr(xoval,);

}

inline void add(int u,int v,int w){

  e[cnt]=(Edge){v,head[u],w};head[u]=cnt++;

}

void dfs(int u,int pre,ll nowval){     //得到根到所有点的异或值

  xoval[u]=nowval;

  for(int i=head[u];~i;i=e[i].nxt){

    int v=e[i].to;

    if(v==pre)continue;

    dfs(v,u,nowval^e[i].w);

  }

}

inline void Insert(ll x){

  int now=;

  for(int i=;i>=;i--){

    int to=(x>>i)&;

    if(!nxt[now][to])nxt[now][to]=++pos;

    now=nxt[now][to];

    //num[now]++;

  }

}

/*inline void del(ll x){      //将01字典树中删除x

    int now=1;

    for(int i=30;i>=0;i--){

        int to=(x>>i)&1;

        num[now]--;

        now=nxt[now][to];

    }

}*/

inline ll query(ll x){

  int now=;ll ans=;

  for(int i=;i>=;i--){

    int to=(x>>i)&;

    if(nxt[now][to^])now=nxt[now][to^],ans+=(<<i);

    else now=nxt[now][to];

  }

  return ans;

}

int main(){

  while(~scanf("%d",&n)){

    init();

    rep(i,,n-){

        int u,v;ll w;read(u);read(v);read(w);

        add(u,v,w);add(v,u,w);

    }

    dfs(,-,);

    ll ans=-1e18;

    rep(i,,n-){

        ll res=query(xoval[i]);

        ans=max(ans,res);

        Insert(xoval[i]);

    }

    printf("%lld\n",ans);

  }

}

巴特西

POJ 3764 The xor-longest Path (01字典树)

最新文章

热门文章