01tire+ chain forward star +dfs+ greedy exercise one

The longest XOR path

Title Description

Given a tree $n$ A weighted tree with two points , Node subscript from $1$ Start to $n$. Look for two nodes in the tree , Find the longest XOR path .

XOR path refers to the XOR of all edge weights on the unique path between two nodes .

Input format

The first line is an integer $n$, Represents the number of points .

Next $n-1$ That's ok , give $u,v,w$ , Each represents... On the tree $u$ Point and $v$ Point has edge , The weight of the edge is $w$.

Output format

a line , An integer represents the answer .

Examples #1

The sample input #1

4
1 2 3
2 3 4
2 4 6

Sample output #1

7

Tips

The longest XOR sequence is $1,2,3$, The answer is $7=3\oplus 4$.

Data range

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

The process is all in the notes

#include<bits/stdc++.h>
using namespace std; 
const int N=6e5+10;
typedef long long ll;
int son[N][2],idx=1,s=0;
int n,head[N],dis[N],nt[N],to[N],weight[N],cnt;
void add(int u,int v,int w){
    // Chain forward star edge 
	nt[++cnt]=head[u];
    head[u] = cnt;
    to[cnt]=v;
    weight[cnt]=w;
}
void insert(int k){
    
	int p=1;
	for(int i=30;i>=0;i--){
    // Due to the scope of the topic w<2^31, So for XOR and just 30 Who can 
		int u=k>>i&1;// obtain k Of the i A binary value 
		if(!son[p][u]) son[p][u]=++idx;// View the current node p Child nodes of u Whether the number has been given , If there is no mark, it will be numbered 
		p=son[p][u];// Move to the next node conversion position 
	}
}
void dodo(int k){
    
	int p=1,da=0;
	for(int i=30;i>=0;i--){
    
		int u=k>>i&1;// obtain k Of the i A binary value 
		// The current in trie Node of tree u; u My two sons are son[u][0/1];
		// Our greedy consideration 
		//trie The tree goes down from the top , Corresponding to binary bits from high to low 
		// And we hope that the high binary bits will be XOR as much as possible 1
		// That is to say, we are trie As the tree goes down from its roots , Try to choose an XOR that allows the current one to get 1 The path of 
		if(son[p][u^1]){
    // XOR has the characteristic that two identical numbers of XOR are equal to no XOR ;  In order for this XOR to get 1, We need to go to the next level of traversal son[p][u^1]
			p=son[p][u^1];// There is son[p][u^1], Then greedily select and move to the next node conversion position 
			da|=(1<<i);//da Store answers , Here will be da Of the i Binary bit assignment 1
		}
		else p=son[p][u];// If it doesn't exist son[p][u^1], We can only give up this one , Go to son[p][u]
	}
	s=max(s,da);// Update answers 
}
void dfs(int u,int v){
    // seek dis Array for conversion 
	insert(dis[u]);// Insert the binary digits of this value trie In the tree 
	dodo(dis[u]);// From the top down , Greedy choice , Update answers 
	for(int i=head[u];i;i=nt[i]){
    // Traverse to i For the starting edge 
		int vv=to[i];// Arrival point 
		if(vv==v) continue;
		dis[vv]=dis[u]^weight[i];// XOR all edge weights on the unique path between two nodes 
		dfs(vv,u);// Continue to drill down 
	}
}
int main(){
    
	cin>>n;
	for(int i=1;i<n;i++){
    
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);// Chain forward star plus two-way edge , In all directions 
        add(v,u,w);
	}
	dfs(1,0);// The title shows , Node from 1 Start 
	cout<<s;
	return 0;
}