logo AlgoBeat OnlineJudge
登录 注册

#216571. 【四川省集】仙人掌最小值查询

内存限制:1024 MiB 时间限制:1500 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

给出一颗带边权的无向连通边仙人掌,多次询问两点之间的点不重复的路径的边权异或和的最小值。

注意:原图可能有重边和自环。一对重边构成的环也被认为是环,自环显然不影响这道题。

输入格式

第一行三个整数 ,其中 表示点数, 表示边数, 表示询问数。

接下来 行,每行三个整数 ,表示在 之间有一条边权为 的边。

接下来 行,每行两个整数 ,表示询问 之间的点不重复路径的边权异或值的最小值。

输出格式

行,每行一个整数,依次表示第 次询问的答案。

样例

样例输入 1

4 4 3
1 2 1
2 3 2
3 4 3
4 2 4
1 4
1 3
2 4

样例输出 1

0
3
1

数据范围与提示

样例解释

第一个询问:

第二个询问:

第三个询问:

数据范围

对于所有数据,,具体范围如下:

Subtask 分值

特别说明

本题数据不是很好造,而且有很多种错误的或者时间复杂度偏高的解法,因此可能较为卡常。欢迎提交 Hack 数据!

目前不保证被卡掉的常见错误解法:

  1. 我试试 能不能过?
  2. 我认为 的重链剖分可以过?
  3. 我猜测 的长链剖分/倍增线性基可以过?
  4. 我觉得 的树分块+线性基可以过?
  5. 各种边界问题一类的。