LuoGuP4551最长异或路径

以你之姓@ 2023-06-02 11:58 0阅读 0赞

[LuoGuP4551最长异或路径][LuoGuP4551]  
\\(01Trie\\)裸题,懒得写\\(solution\\)了,直接贴代码吧,好懒啊yyy.  
\\(Code:\\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 1e5 + 100 ; const int maxsize = 1 << 30 ; struct edge { int to , next , data ; } e[(N<<2)] ; int dis[N] , n , head[N] , tot , ch[N*100][2] , cnt , sum[N*100] , ans ; inline void dfs (int cur , int anc , int dist) { dis[cur] = dist ; for (int i = head[cur] ; i ; i = e[i].next) { int k = e[i].to ; if ( k == anc ) continue ; dfs ( k , cur , dist ^ e[i].data ) ; } return ; } inline void insert (int cur) { int now = 0 ; for (int i = maxsize ; i ; i >>= 1) { bool son = ( ( i & cur ) != 0 ) ? true : false ; if ( ! ch[now][son] ) ch[now][son] = ++ cnt ; now = ch[now][son] ; } ++ sum[now] ; return ; } inline int greedy (int cur) { int now = 0 , res = 0 ; for (int i = maxsize ; i ; i >>= 1) { bool son = ( ( i & cur ) != 0 ) ? false : true ; if ( ! ch[now][son] ) son ^= 1 ; res = ( res << 1 | son ) ; now = ch[now][son] ; } return res ; } inline void build (int u , int v , int w) { e[++tot].next = head[u] ; e[tot].to = v ; e[tot].data = w ; head[u] = tot ; return; } signed main (int argc , char * argv[] ) { n = rint () ; rep ( i , 2 , n ) { int u = rint () , v = rint () , w = rint () ; build ( u , v , w ) ; build ( v , u , w ) ; } dfs ( 1 , 0 , 0 ) ; rep ( i , 1 , n ) insert ( dis[i] ) ; rep ( i , 1 , n ) ans = max ( ans , dis[i] ^ greedy ( dis[i] ) ) ; printf ("%lld\n" , ans ) ; system ("pause") ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11459884.html

[LuoGuP4551]: https://www.luogu.org/problem/P4551