首页 > 代码库 > CODEVS1187 Xor最大路径 (字典树)

CODEVS1187 Xor最大路径 (字典树)

  由于权值是在边上,所以很容易发现一个性质:d(x,y)=d(x,root) xor d(y,root)。

  因为有了这个性质,那么就很好做了。对于每一个点统计到root的距离,记为f 数组。

  将f数组里的每个值插进按照二进制位插进字典树里面。

  枚举每一个点,然后在字典树中搜索最大的xor值就可以了。

Program CODEVS1187;const maxn=100008;type arr=record        u,v,w,next:int64;        end;type arr1=record        next:array[0..1] of longint;        end;var eg:array[0..maxn*2] of arr;    last:array[0..maxn] of longint;    fa:array[0 ..maxn] of longint;    f:array[0..maxn] of int64;    T:array[0..maxn*32] of arr1;    a:array[0..100] of longint;    n,u,v,w,root,mx,num,m,k,sum,ans,now:int64;    i,j:longint;procedure add(u,v,w:longint);begin  inc(j);  eg[j].u:=u;  eg[j].v:=v;  eg[j].w:=w;  eg[j].next:=last[u];  last[u]:=j;end;procedure dfs(u:longint;sum:int64;fa:longint);var i:longint;begin  f[u]:=sum;      i:=last[u];  while i<>0 do    begin      if eg[i].v<>fa then      dfs(eg[i].v,sum xor eg[i].w,u);      i:=eg[i].next;    end;end;begin  readln(n);  for i:=1 to n-1 do    begin      readln(u,v,w);          add(u,v,w);      add(v,u,w);    end;  root:=1;  dfs(root,0,0);{---------------------------------------------------}  mx:=0;  for i:=1 to n do if f[i]>mx then mx:=f[i];  j:=mx; num:=0;  while j>0 do    begin      inc(num);      j:=j div 2;    end;  m:=num; k:=1;  for i:=1 to n do    begin      fillchar(a,sizeof(a),0);      j:=f[i]; num:=0;      while j>0 do        begin          inc(num);          a[num]:=j mod 2;          j:=j div 2;        end;      now:=1;      for j:=m downto 1 do        if T[now].next[a[j]]<>0 then now:=T[now].next[a[j]] else          begin            inc(k);            T[now].next[a[j]]:=k;            now:=k;          end;    end;  ans:=0;  for i:=1 to n do    begin      fillchar(a,sizeof(a),0);      j:=f[i]; num:=0;      while j>0 do        begin          inc(num);          a[num]:=j mod 2;          j:=j div 2;        end;      now:=1; sum:=0;      for j:=m downto 1 do        if T[now].next[1-a[j]]<>0 then          begin            sum:=sum*2+1-a[j];            now:=T[now].next[1-a[j]];          end        else          begin            sum:=sum*2+a[j];            now:=T[now].next[a[j]];          end;      if sum xor f[i]>ans then ans:=sum xor f[i];    end;  writeln(ans);end.

 

CODEVS1187 Xor最大路径 (字典树)