題目描述

給定一棵?nn?個點的帶權樹，結點下標從?11?開始到?NN?。尋找樹中找兩個結點，求最長的異或路徑。

異或路徑指的是指兩個結點之間唯一路徑上的所有節點權值的異或。

輸入輸出格式

輸入格式：

?

第一行一個整數?NN?，表示點數。

接下來?n-1n?1?行，給出?u,v,wu,v,w?，分別表示樹上的?uu?點和?vv?點有連邊，邊的權值是?ww?。

?

輸出格式：

?

一行，一個整數表示答案。

?

輸入輸出樣例

輸入樣例#1：?
4 1 2 3 2 3 4 2 4 6 輸出樣例#1：?
7

說明

最長異或序列是1-2-3，答案是 7 (=3 ⊕ 4)

數據范圍

1\le n \le 100000;0 < u,v \le n;0 \le w < 2^{31}1≤n≤100000;0<u,v≤n;0≤w<2^31

?

?

? ? 為什么不叫trie樹模板題呢？？？

? ? 練練板子hhhh

?

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=100005; int ci[35],n,m,Xor[maxn],c=0,ch[maxn*57][2],R=0,A=0; int to[maxn*2],ne[maxn*2],val[maxn*2],num,hd[maxn]; inline void add(int x,int y,int z){ to[++num]=y,ne[num]=hd[x],hd[x]=num,val[num]=z;}inline void Ins(int x){int now=R;for(int i=30,u;i>=0;i--){u=(ci[i]&x)?1:0;if(!ch[now][u]) ch[now][u]=++c;now=ch[now][u];} }int F(int x){int now=R,an=0;for(int i=30,u;i>=0;i--){u=(ci[i]&x)?0:1;if(ch[now][u]) an+=ci[i],now=ch[now][u];else now=ch[now][u^1];}return an; }void dfs(int x,int fa){A=max(A,F(Xor[x])),Ins(Xor[x]);for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa){Xor[to[i]]=Xor[x]^val[i];dfs(to[i],x);} }int main(){ci[0]=1;for(int i=1;i<=30;i++) ci[i]=ci[i-1]<<1;scanf("%d",&n);int uu,vv,ww;for(int i=1;i<n;i++) scanf("%d%d%d",&uu,&vv,&ww),add(uu,vv,ww),add(vv,uu,ww);dfs(1,-1);printf("%d\n",A);return 0; }

　　

轉載于:https://www.cnblogs.com/JYYHH/p/9026855.html

總結

以上是生活随笔為你收集整理的洛谷 P4551 最长异或路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。