洛谷傳送門

文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

本題關(guān)鍵就在于一點(diǎn)：
若把每個(gè)點(diǎn)的深度dep[i]定義為從根到節(jié)點(diǎn)邊權(quán)的異或和
那么i到j(luò)的路徑異或和可以表示為：

dep[i] ^ dep[j]

首先要是i、j在不同子樹上顯然成立
如果他們?cè)谕蛔訕渖?#xff0c;那么它們到根的公共部分異或兩遍會(huì)抵消
所以也是成立的

這樣dfs一遍求出dep數(shù)組
本題就變成01trie的模板題了

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long typedef unsigned long long ull; const int N = 1e6+100; const int M=1e7+5; const int mod=1e9+7; int n,m; int tr[N][3],tot=1,end[N]; int fi[N],cnt=-1; struct node{int to,nxt,v; }p[N<<1]; void addline(int x,int y,int v){p[++cnt]=(node){y,fi[x],v};fi[x]=cnt; } int dep[N]; void dfs(int x,int f){for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dep[to]=dep[x]^p[i].v;dfs(to,x);}return; } int mi[33]; int s[33],k; void build(int o){for(int i=0;i<=30;i++){s[i]=o&mi[i]?1:0;}int p=1;for(int i=30;i>=0;i--){if(!tr[p][s[i]]) tr[p][s[i]]=++tot;p=tr[p][s[i]];}end[p]++; }int ask(int o){for(int i=0;i<=30;i++){s[i]=o&mi[i]?1:0;}int p=1,res=0;for(int i=30;i>=0;i--){int now=s[i];if(tr[p][!now]){p=tr[p][!now];res+=mi[i];}else p=tr[p][now];}return res; } int main(){mi[0]=1;for(int i=1;i<31;i++) mi[i]=mi[i-1]<<1;memset(fi,-1,sizeof(fi));scanf("%d",&n);for(int i=1;i<n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);addline(a,b,c);addline(b,a,c);}dfs(1,0);for(int i=1;i<=n;i++){build(dep[i]);}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,ask(dep[i]));}printf("%d",ans);return 0; } /* 9 6 10 5 6 2 10 10 7 3 2 9 1 4 4 3 2 16 4 10 3 5 2 7 1 9 3 8 2 10 */

總結(jié)

以上是生活随笔為你收集整理的YBTOJ洛谷P4551：最长异或路径（trie树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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