首页 > 代码库 > 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最大路径 (字典树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。