题目描述（POJ1986）： 约翰有 N 个农场，标记为1～ N 。有 M 条垂直和水平的道路连接农场，每条道路的长度各不相同。每个农场都可以直接连接到北部（N）、南部（S）、东部（E）或西部（W）最多4个其他农场。农场位于道路的终点，正好一条道路连接一对农场，没有两条道路交叉。他希望知道两个农场之间的道路长度，农场的地图如下图所示。“1 6 13 E”表示从F1到F6有一条长度为13的道路，F6在F1的东部。

输入： 第1行包含两个整数 N （2≤ N ≤40,000）和 M （1≤ M <40,000）。第2.. M +1行，每行都包含4个字符 a、b、l、d ，表示两个农场 a 和 b 由一条路相连，长度为 l （1≤ l ≤1000）， d 是字符“N”“S”“E”或“W”，表示从 a 到 b 的道路方向。第 M +2行包含单个整数 K （1≤ K ≤10,000），表示查询个数。接下来的 K 行，每行都包含距离查询的两个农场的编号。

输出： 对每个查询，都单行输出两个农场的距离。

题解： 本题实际上为树上距离查询问题，可以采用Tarjan算法离线处理所有查询。

1. 算法设计

（1）根据输入数据采用链式前向星存储图。

（2）采用Tarjan算法离线处理所有查询。 QQKa+3Orq+3+x70f6181OBJuQRmbIP0EKX5W6JoJj7KpYJEcyNsDikWXh7j66hZm

2. 算法实现