UOJ Logo

NOI.AC

#41. 最短路

统计

C. 最短路

题目描述

小W有一棵 $n$ 个点的带权树,现在他想从 $S$ 走到 $T$。定义一条路径的长度为上面所有边的长度的异或和(如果不知道异或是什么可以戳 Wikipedia,异或和就是所有数异或的和)。

但是他觉得直接沿着树上的边走太慢了,于是他决定新建一些边。他有 $m$ 个修建计划,第 $i$ 个是在 $u$ 和 $v$ 之间修建一条长为 $w$ 的边。

现在他有一些询问,每个询问形如 $S, T, l, r$,表示如果动用 $[l,r]$ 区间内的所有修建计划,他从 $S$ 走到 $T$ 的最短路长度应该是多少。

输入格式

第一行三个整数 $n$,$m$,$q$。

接下来 $n-1$ 行,每行三个整数 $u$,$v$,$w$,表示原本树上有一条 $u$ 和 $v$ 之间有一条长度为 $w$ 的边。

接下来 $m$ 行,第 $i$ 行有三个整数 $u$,$v$,$w$,表示一个修建计划。

接下来 $q$ 行,每行四个整数 $S$,$T$,$l$,$r$,表示一组询问。

输出格式

输出共 $q$ 行,表示每组询问的答案。

样例1

input

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

output

0
0
1

限制与约定

对于 $20\%$ 的数据,$n, m, q \le 1000$。

对于 $50\%​$ 的数据,$n, m, q \le 5 * 10^4​$。

对于 $100\%$ 的数据,$1 \le n, m, q \le 3 * 10^5, 1 \le w \le 10^9$。

时间限制:3s

空间限制:512MB

提示

输入输出量可能很大,请使用较快的I/O方式。

下载

样例数据下载