#P3364. [Usaco2004 Feb]Distance Queries 距离咨询

[Usaco2004 Feb]Distance Queries 距离咨询

题目描述

有 NN 个农场,编号为 11 到 NN。它们由 MM 条双向道路连接,任意两个农场之间恰有一条简单路径。两农场的距离是这条路径上各条道路长度之和。

2≤N≤400002\le N\le40000,M=N−1M=N-1。每条道路的长度是 11 到 10001000 的整数。

给定 KK 次询问,每次求两座农场之间的距离。

输入格式

第一行两个整数 N,MN,M。

接下来 MM 行,每行两个农场编号 u,vu,v、一个道路长度 LL 和一个字符 DD。字符 N、E、S、W 表示从 uu 到 vv 的方位。每条道路均可双向通行。

接下来一行给出询问数 KK,满足 1≤K≤1041\le K\le10^4。随后 KK 行,每行两个农场编号。

输出格式

对每次询问输出一行一个整数,表示两座农场之间的距离。

样例

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6
1 4
2 6
13
3
36

同场地图定义(Navigation Nightmare)

题目来源