思路

  此题主要考查树的构建与异或运算的基本性质，将树构建完毕后，可以去求出从根节点到每一个节点中所有边权的异或，假设根节点是t，当前要查询的点为u，那么对于点x，它到点u的边权异或等于它到t点的所有边权异或与u点到t的所有边权异或的异或，然后根据异或运算的性质，点u到t点的边权异或与k值的异或即为任意点x到根节点的异或，此时，两点之间的边权异或值即为k

代码

c++

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>

题目内容

小红有一棵由$n$个节点、$n-1$条无向边构成的树，每条边的权值为$w_i$。

定义树上两个点$(u,v)$的权值为，从$u$到$v$的简单路径上，全部边权的异或和，特别的，当$u$和$v$为同一个点时，权值为$0$。

小红会提出$q$次询间，每次询问要求计算有多少个点到节点$u$的权值恰好为$k$。

树是指这样的一张图，其上的任意两个点都连通，且不存在环。

简单路径是指两个节点之间的一条路径，其不包含任何重复的节点。

也就是说，在简单路径上每个节点只能出现一次。

输入描述

第一行输入两个整数 $n,q(1≤n,q≤10^5)$，分别表示节点总数和询问次数。

此后 $n-1$行，第$i$行输入三个整数$u_i,v_i$和$w_i$(1≤u_i,v_i≤n;u_i≠v_i;0≤w<2^60)表示树

上第$i$条边连接节点$u_i$和$v_i$目边权为$w_i$。保证树联通，没有重边。

此后$q$行，每行输入两个整数$u,k(1≤u≤n,0≤k<2^{60})$代表被询问的节点和限定。

输出描述

对于每一个询问，在一行上输出一个整数，代表到节点$u$的权值恰好为$k$的节点数量。

样例1

输入

3 2
1 2 2
1 3 3
1 0
2 2

输出

1
1