P4551 最长异或路径（XOR 异或 dfs 字典树 trie 贪心）
题目链接：最长异或路径 - 洛谷
题目描述
给定一棵 n 个点的带权树，结点下标从 1 开始到 n。寻找树中找两个结点，求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 nn，表示点数。
接下来 n-1n−1 行，给出 u,v,w ，分别表示树上的 u 点和 v 点有连边，边的权值是 w。
输出格式
一行，一个整数表示答案。
输入输出样例
输入 #1复制
41 2 32 3 42 4 6
输出 #1复制
7
题解：
一个数，如果它两次异或同一个数，那么它是不会有改变的。
那么i~j的路径上的异或和，就可以表示成根到i的异或和异或上根到j的异或和。
那思路就很明确了：将根节点到每个节点的路径权值异或和insert到trie里，再在trie里找异或最大值；那么我们在trie中对于每一位进行贪心，从高位到低位，如果这一位有一个与它不同的，即异或 后是1，那我们就顺着这条路往下走；否则就顺着原路往下走。
因为高位决定答案，所以此贪心策略正确；
代码如下：
/*Keep on going Never give up*/#include using namespace std;#define int long long#define pi acos(-1.0)inline int read(){ int x=0,k=1; char c=getchar(); while(c'9'){if(c=='-')k=-1;c=getchar();} while(c>='0'&&c<='9')x=(x<<3)+(x<=0;i--){bool t=(1&(x>>i));if(!trie[now][t]) trie[now][t]=++toot;now=trie[now][t];}return ;}void add(int x,int y,int z){nxt[++tot]=head[x];val[tot]=y;edge[tot]=z;head[x]=tot;}void dfs(int x,int fa){for(int i=head[x];i;i=nxt[i]){int v=val[i],zz=edge[i];if(v!=fa){//printf("%lld -> %lld\n",x,v);_xors[v]=_xors[x]^zz;dfs(v,x);}}return ;}int ask(int x){int ans=0,now=0;for(int i=31;i>=0;i--){bool ttt=((x>>i)&1);if(trie[now][(ttt^1)]){ans+=(1<<i);now=trie[now][(ttt^1)];}elsenow=trie[now][ttt];}return ans;}signed main(){ n=read();for(int i=1;i<n;i++){int x=read(),y=read(),z=read();add(x,y,z);add(y,x,z);}int res=-11;dfs(1,0);/*for(int i=1;i<=n;i++){cout<<i<<" "<<_xors[i]<<endl;}*/for(int i=1;i<=n;i++)_insert(_xors[i]);for(int i=1;i<=n;i++){res=max(res,ask(_xors[i]));}cout<<res;}trie和dfs还是要多写啊，不然出错要改好久QwQ