題目：

題目背景

OURCE：NOIP2015-SHY-7

題目描述

求一棵帶邊權的樹的一條最大?Xor?路徑的值。這里的“路徑”不一定從根到葉子結點，中間一段路徑只要滿足條件也可以。

輸入格式

第一行，一個整數?N?，表示一顆樹有?N?個節點，接下來?N-1?行，每行三個整數?a,b,c?表示節點?a?和節點?b?之間有條權值為?c?的邊。

輸出格式

輸出僅一行，即所求的最大值。

樣例數據 1

輸入　 [復制]

4?
1 2 3?
1 3 4?
1 4 7

輸出

7

備注

【數據范圍】
對?40%?的輸入數據?：數據退化為一條鏈；
另對?10%?的輸入數據?：N≤1000；
對?100%?的輸入數據?：1≤N≤100000，?c≤231-1。

題解：

套路題

首先預處理出所有點到根節點的異或和XOR····然后將其轉化成二進制從高位到低位儲存到trie樹上··容易想到兩個點的XOR的異或和就是這兩個點的路徑的異或和····所以枚舉每一個XOR,在trie樹上走，從高位開始查找與起位置上的數相反的數是否存在···如果存在優先選擇···一邊走一邊計算答案即可

代碼：

#include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cctype> #include<string> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int N=1e5+5; const int M=4e6+5; int fst[N],go[N*2],nxt[N*2],val[N*2],tot,n,xo[N],maxx,len; struct node {int son[2]; }tr[M]; inline int R() {char c;int f=0;for(c=getchar();c<'0'||c>'9';c=getchar());for(;c<='9'&&c>='0';c=getchar())f=(f<<3)+(f<<1)+c-'0';return f; } inline void comb(int a,int b,int v) {nxt[++tot]=fst[a],fst[a]=tot,go[tot]=b,val[tot]=v;nxt[++tot]=fst[b],fst[b]=tot,go[tot]=a,val[tot]=v; } inline void dfs(int u,int fa) {for(int e=fst[u];e;e=nxt[e]){int v=go[e];if(v==fa) continue;xo[v]=xo[u]^val[e];dfs(v,u);} } inline void insert(int x) {int po=0; for(int i=len-1;i>=0;i--){int temp=(x>>i)&1;if(!tr[po].son[temp]) tr[po].son[temp]=++tot;po=tr[po].son[temp];} } inline int check(int x) {int ans=x,po=0;for(int i=len-1;i>=0;i--){int temp=(x>>i)&1;if(tr[po].son[temp^1]) ans|=(1<<i),po=tr[po].son[temp^1];else ans^=(temp<<i),po=tr[po].son[temp];}return ans; } int main() {//freopen("a.in","r",stdin);n=R();int a,b,c;for(int i=1;i<n;i++) {a=R(),b=R(),c=R();maxx=max(maxx,c);comb(a,b,c);}dfs(1,0);int temp=maxx;while(temp) temp/=2,len++;tot=0;for(int i=2;i<=n;i++) insert(xo[i]); for(int i=2;i<=n;i++)maxx=max(maxx,check(xo[i]));cout<<maxx<<endl;return 0; }

?

轉載于:https://www.cnblogs.com/AseanA/p/7639894.html

總結

以上是生活随笔為你收集整理的刷题总结——xor（ssoj）的全部內容，希望文章能夠幫你解決所遇到的問題。

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