01tire+链式前向星+dfs+贪心练习题.1

最长异或路径

题目描述

给定一棵 $n$ 个点的带权树，结点下标从 $1$ 开始到 $n$。寻找树中找两个结点，求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入格式

第一行一个整数 $n$，表示点数。

接下来 $n-1$ 行，给出 $u,v,w$ ，分别表示树上的 $u$ 点和 $v$ 点有连边，边的权值是 $w$。

输出格式

一行，一个整数表示答案。

样例 #1

样例输入 #1

4
1 2 3
2 3 4
2 4 6

样例输出 #1

7

提示

最长异或序列是 $1,2,3$，答案是 $7=3\oplus 4$。

数据范围

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

过程全部在注释内

#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){
    //链式前向星加边
	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--){
    //由于题目范围w<2^31，所以对于异或和只需要30位即可
		int u=k>>i&1;//得到k的第i个二进制位的值
		if(!son[p][u]) son[p][u]=++idx;//查看当前节点p的子节点u是否已给予编号,没有则标记给予编号
		p=son[p][u];//移至下一节点转换位置
	}
}
void dodo(int k){
    
	int p=1,da=0;
	for(int i=30;i>=0;i--){
    
		int u=k>>i&1;//得到k的第i个二进制位的值
		//当前在trie树的节点u; u的两个儿子是son[u][0/1];
		//我们贪心的考虑
		//trie树从顶向下，对应着二进制位从高到低
		//而我们希望高的二进制位尽可能异或出来是1
		//也就是说我们在trie树从根往下走的过程中，要尽量选择能让当前这一位异或得到1的路径
		if(son[p][u^1]){
    //异或有异或两个相同数等于没异或的特点; 为了让这一位异或得到1，我们下一层遍历就需要去son[p][u^1]
			p=son[p][u^1];//存在son[p][u^1],则贪心选择并移至下一节点转换位置
			da|=(1<<i);//da存储答案，此处将da的第i个二进制位赋1
		}
		else p=son[p][u];//如果实在不存在son[p][u^1],我们就只能放弃这一位，去son[p][u]
	}
	s=max(s,da);//更新答案
}
void dfs(int u,int v){
    //求dis数组做转化用
	insert(dis[u]);//将此值二进制各位数插入trie树中
	dodo(dis[u]);//从顶向下，贪心选择，更新答案
	for(int i=head[u];i;i=nt[i]){
    //遍历以i为起点的边
		int vv=to[i];//到达点
		if(vv==v) continue;
		dis[vv]=dis[u]^weight[i];//进行两个结点之间唯一路径上的所有边权的异或
		dfs(vv,u);//继续深入遍历
	}
}
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);//链式前向星加双向边，无论有向无向
        add(v,u,w);
	}
	dfs(1,0);//题目所示，结点从1开始
	cout<<s;
	return 0;
}