让我们异或吧 DFS + 位运算技巧

el/2024/5/23 1:31:52

题意

中文题意就不需要分析了吧

分析

我在洛谷上面搜的是LCA的标签,但是这道题跟LCA好像关系不太大?
首先因为有n - 1条边,首先我们可以确定这是一条树,然后我们去求异或值的时候,可以先求出点到跟节点的异或值,然后把待求的两点跟根节点之间的异或值异或一下就好了,因为重复的部分会进行抵消

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 100010;
int num[N];
int h[N],ne[N * 2],e[N * 2],w[N * 2],idx;
int f[N][21];
int d[N];
int n,m;void add(int a,int b,int c){ne[idx] = h[a],e[idx] = b,w[idx] = c,h[a] = idx++;
}void dfs(int u,int fa,int res){num[u] = res;for(int i = h[u];~i;i = ne[i]){int j = e[i];if(j == fa) continue;dfs(j,u,res ^ w[i]);}
}int main(){scanf("%d",&n);memset(h,-1,sizeof h);for(int i = 0;i < n - 1;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dfs(1,1,0);scanf("%d",&m);while(m--){int x,y;scanf("%d%d",&x,&y);printf("%d\n",num[x] ^ num[y]);}return 0;
}/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

http://www.ngui.cc/el/5239357.html

相关文章

松鼠的新家 LCA + 树上差分

题意 中文题意就不需要分析了吧 分析 首先两点之间&#xff0c;我们应该去走最短路径最能得到最优解&#xff0c;所以很容易想到求LCA&#xff0c;假设两点分别为x&#xff0c;y&#xff0c;LCA(x,y) u&#xff0c;所以只需要把路径 x -> u -> y上的所有点加上一个糖…

Alyona and a tree 树上差分 +倍增

传送门 题目描述 给定一颗树&#xff0c;每个结点有对应点权&#xff0c;每条边也有对应边权。如果dis<v, u> < val[u]&#xff0c;则说明结点u被结点v所管辖。对于每个结点&#xff0c;输出它管辖的结点数目。 分析 这道题如果我们遍历每一个点并且往上爬&#x…

Snacks dfs 序 + 线段树

传送门 题目描述 百度科技园内有n个零食机&#xff0c;零食机之间通过n−1条路相互连通。每个零食机都有一个值v&#xff0c;表示为小度熊提供零食的价值。 由于零食被频繁的消耗和补充&#xff0c;零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发&#xff0…

Count on a tree 主席树 + LCA

传送门 题目描述 给定一个包含 N 个结点的树. 树节点从 1 到 N编号.。每个节点有一个整数权值&#xff0c;查询从节点 u 到节点 v的路径上权值第k小的节点的权值。 分析 树上主席树的入门题了 我们可以用类似于树上差分的思想来处理这个问题&#xff0c;每一个节点其实就是…

Super Mario 主席树 +二分

传送门 题目描述 马里奥是一个举世闻名的管道工&#xff0c;他的跳跃能力让我们钦佩。在一条长度为n的道路上&#xff0c;在每个整数点i的位置都有一个高度为hi的障碍物。现在的问题是&#xff1a;假设马里奥可以跳跃的最高高度为H&#xff0c;在道路的[L,R] 区间内他可以跳跃…

The Door Problem 并查集

传送门 题目描述 ​有n个门和m个开关&#xff0c;每个开关可以控制任意多的门&#xff0c;每个门严格的只有两个开关控制&#xff0c;问能否通过操作某些开关使得所有门都打开。&#xff08;给出门的初始状态&#xff09;。 分析 一开始看的时候觉得是个2—sat问题&#xf…

Generate a String 线性DP + 单调队列优化

传送门 题目描述 给定正整数 n, x, y&#xff0c;你要生成一个长度为 n 的字符串&#xff0c;有两种操作&#xff1a; 添一字符或删去一个原有字符&#xff0c;代价为 x&#xff1b; 将已有字串复制粘贴一次&#xff08;翻倍&#xff09;&#xff0c;代价为 y。 求最小代价。…

Three Paths on a Tree 树的直径

传送门 题目描述 在一棵树内找三个点x,y,z&#xff0c;要求三个点之间的距离最大&#xff0c; 分析 首先我们可以找到这棵树内的直径&#xff0c;然后去去找另一点到这棵树上的直径最短 我一开始的思路是三次bfs&#xff0c;求出直径的端点&#xff0c;并且处理出每一个点…

Number of Components 思维

传送门 题目描述 分析 在一条链中&#xff0c;可以观察出结论&#xff1a;联通块数 点数 - 边数 所以我们需要求出每个点的贡献以及每一条边的贡献 首先&#xff0c;每一个点只有在 a[i] > l && a[i] < r 的时候才会被选择&#xff0c;所以每一个点的贡献应该…

To the moon 主席树 + 标记永久化

传送门 题目描述 给你一串序列&#xff0c;每次对它有四种操作&#xff0c; 1. 将l到r之间所有的数d&#xff0c;同时时间戳1。 2. 查询当前时间戳下l到r的所有数的总和。 3…查询时间戳d下的l到r的所有数的和。 4.将时间戳返回至t。 分析 主席树标记永久化的板子题了&…