时间限制:4000ms
单点时限:2000ms
内存限制:256MB
描述
有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？
输入
输入数据的第一行包含一个整数 T，表示数据组数。
接下来有 T 组数据，每组数据中：
第一行包含一个整数 N，表示树上节点的个数（从 1到 N标号）。
接下来的 N-1 行包含三个整数 a, b, len，表示有一根长度为 len的树枝/树干在节点 a和节点 b 之间。
接下来一行包含一个整数 M，表示询问数。
接下来M行每行两个整数 S, T，表示毛毛虫从 S爬行到了 T，询问这段路程中的树枝/树干是否能拼成三角形。
1 ≤ T ≤ 5
小数据：1 ≤ N ≤ 100, 1 ≤M ≤ 100, 1 ≤ len ≤ 10000
大数据：1 ≤ N ≤ 100000,1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000
输出
对于每组数据，先输出一行"Case#X:",其中X为数据组数编号，从 1开始。
接下来对于每个询问输出一行，包含"Yes"或“No”，表示是否可以拼成三角形。
更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
样例输入
2
5
1 2 5
1 3 20
2 4 30
4 5 15
2
3 4
3 5
5
1 4 32
2 3 100
3 5 45
4 5 60
2
1 4
1 3
样例输出
Case #1:
No
Yes
Case #2:
No
Yes
这个题昨天做的时候总是报RE，也就是运行时错误Runtime Error，原因是它那个测试系统不允许创建多个类，即使是内部类也不行，办法就是改写成数组形式表示。
补充一下：创建多个类是可以的，这里不行可能是堆溢出或则其他问题，希望不要误导了大家。最后结果TLE了，还是要改进一下的。
思路：
1、读取数据，建立图
2、广度优先遍历，找到目的点。这个过程找到的肯定是最短路，因为这是一棵树，两点之间只有一条通路（不重复的情况下）。遍历过程中保存每个点遍历的时候的父亲节点，这样就能够知道走过了哪些节点。
3、遍历任意三条边的组合是否能够组成三角形。
我自己创建了一些测试数据，感觉大数据时应该也还可以，不会超时。只有最后一步看似效率比较低，实际上有的文章说，当边数超过50时，一定能够组成三角形，所以实际上它每次都不会遍历那么多次就返回了。