題目：

給定一棵n個點(diǎn)的帶權(quán)樹，結(jié)點(diǎn)下標(biāo)從1開始到N。尋找樹中找兩個結(jié)點(diǎn)，求最長的異或路徑。
異或路徑指的是指兩個結(jié)點(diǎn)之間唯一路徑上的所有邊權(quán)的異或。

輸入格式

第一行一個整數(shù)NN，表示點(diǎn)數(shù)。

接下來 n?1 行，給出 u,v,w ，分別表示樹上的 u 點(diǎn)和 v 點(diǎn)有連邊，邊的權(quán)值是 w。

輸出格式

一行，一個整數(shù)表示答案。

輸入輸出樣例

輸入 #1

4
1 2 3
2 3 4
2 4 6

輸出 #1

7

說明/提示

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

數(shù)據(jù)范圍

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

分析：

復(fù)習(xí) 01trie：
是trie的一種。每個節(jié)點(diǎn)是0或者1，我們可以將一些數(shù)以二進(jìn)制表示的形式存入01trie，進(jìn)而解決一些異或問題。有關(guān)trie樹的原理再次不在贅述。
異或，指一個法則：

兩個數(shù)的二進(jìn)制數(shù)位上相等即為0，不相等即為1。

顯然，一個數(shù)對同一個數(shù)異或兩次等于沒有異或，那么異或也就滿足交換律，結(jié)合律。

對于一列數(shù)的異或和，我們可以將其用結(jié)合律從1$～$i，i+1$～$j進(jìn)行異或，然后在將這兩個結(jié)果進(jìn)行異或，結(jié)果不變。
于是我們可以：

處理出1到每一個節(jié)點(diǎn)的異或和

把他們加到一棵(01trie)里面

從高位到低位貪心操作，取最大值，即是答案。

AC代碼：

#include<bits/stdc++.h> using namespace std; const int N=1e5+10;int head[N], nxt[N<<1], to[N<<1], weight[N<<1], cnt; int n, dis[N], ch[N<<4][2], tot = 1, ans;void insert(int x){for (int i=30,u=1;i>=0;--i){//由題目，是w<2^31,所以對于異或和只需要30位即可int c=((x>>i)&1);if (!ch[u][c])ch[u][c]=++tot;u=ch[u][c];} }void get(int x){int res=0;for(int i=30,u=1;i>=0;--i){int c=((x>>i)&1);if(ch[u][c^1]){u=ch[u][c^1];res|=(1<<i);}elseu=ch[u][c];}ans=max(ans,res); } void add(int u, int v, int w){nxt[++cnt]=head[u];head[u] = cnt;to[cnt]=v;weight[cnt]=w; }void dfs(int u,int fa) {insert(dis[u]);//處理出1到每一個節(jié)點(diǎn)的異或和,把他們加到一棵\(01trie\)里面get(dis[u]);for (int i=head[u];i;i=nxt[i]){int v=to[i];if (v==fa)continue;dis[v]=dis[u]^weight[i];dfs(v, u);//用dfs(v,u)表示v和u之間的路徑的邊權(quán)異或和} }int main() {scanf("%d", &n);for (int i=1;i<n;++i){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);}dfs(1,0);//設(shè)定0為根節(jié)點(diǎn),但實(shí)際根節(jié)點(diǎn)是1；printf("%d", ans);return 0; }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。