题目描述
有一棵包含 n 个节点的树,每条边上都标有一个未知的整数,范围为 [0,260−1]。
现在依次收到 m 条约束。每条约束形如:已知从节点 u 到节点 v 的路径上,所有边权的异或和必须等于 val。
这些约束可能并不全部正确。
定义 p 为满足以下条件的最大整数:
- 前 p 条约束可以同时成立,即存在一种边权分配方案满足它们;
- 而加入第 p+1 条约束后,不再存在满足所有这些约束的边权分配方案;或者 p=m,即不存在第 p+1 条约束。
请求出每组数据对应的 p。
输入格式
第一行包含两个整数 n,m(1≤n,m≤105),分别表示树的节点数和约束数量。
接下来 n−1 行,每行包含两个整数 u,v(1≤u,v≤n),表示一条连接节点 u 与节点 v 的无向边。
接下来 m 行,每行包含三个整数 u,v,val,表示一条约束:
xor(u→v)=val
其中 1≤u,v≤n,且 0≤val<260。
输出格式
输出一个整数 p,表示能够同时满足的最长前缀约束长度。
样例 1 输入
7 5
1 2
2 3
3 4
4 5
5 6
6 7
1 3 1
3 5 0
5 7 1
1 7 1
2 3 2
样例 1 输出
3
数据范围
对于所有测试数据,保证:1≤n,m≤105,1≤u,v≤n,0≤val<260。
| 测试点 |
n≤ |
m≤ |
val< |
特殊性质 |
| 1∼4 |
10 |
23 |
无 |
| 5∼7 |
1000 |
260 |
树是一条链 |
| 8∼9 |
210 |
无 |
| 10∼12 |
105 |
| 13∼15 |
260 |
每个约束中,有 u=1 |
| 16∼20 |
无 |