P16596 【四川省集】仙人掌最小值查询
题目描述
给出一颗带边权的无向连通边仙人掌，多次询问两点之间的点不重复的路径的边权异或和的最小值。
注意：原图可能有重边和自环。一对重边构成的环也被认为是环，自环显然不影响这道题。
输入格式
第一行三个整数 $n,m,k$，其中 $n$ 表示点数，$m$ 表示边数，$k$ 表示询问数。
接下来 $m$ 行，每行三个整数 $l_i,r_i,v_i$，表示在 $l_i,r_i$ 之间有一条边权为 $v_i$ 的边。
接下来 $k$ 行，每行两个整数 $l_i,r_i$，表示询问 $l_i,r_i$ 之间的点不重复路径的边权异或值的最小值。
输出格式
共 $k$ 行，每行一个整数，依次表示第 $i$ 次询问的答案。
说明/提示
### 样例解释
第一个询问：$1\to2\to3\to4,1\bigoplus2\bigoplus3=0$；
第二个询问：$1\to2\to3,1\bigoplus2=3$；
第三个询问：$2\bigoplus3=1$。
### 数据范围
对于所有数据，$n\le5\times10^5,k\le10^5,v\le10^9$，具体范围如下：
| Subtask | $n\le$ | $k\le$ | $v\le$ | 分值 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $0$ | $10$ | $50$ | $2^{5}-1$ | $10$ |
| $1$ | $100$ | $3000$ | $2^{15}-1$ | $20$ |
| $2$ | $10^4$ | $10^5$ | $2^{20}-1$ | $30$ |
| $3$ | $5\times10^5$ | $10^5$ | $2^{30}-1$ | $40$ |
### 特别说明
本题数据不是很好造，而且有很多种错误的或者时间复杂度偏高的解法，因此可能较为卡常。欢迎提交 Hack 数据！
目前不保证被卡掉的常见错误解法：
1. 我试试 $nk\log V$ 能不能过？
2. 我认为 $k\log^4$ 的重链剖分可以过？
3. 我猜测 $k\log^3$ 的长链剖分/倍增线性基可以过？
4. 我觉得 $(n\log n)^{\frac{4}{3}}$ 的树分块+线性基可以过？
5. 各种边界问题一类的。