2013编程之美资格赛之树上的三角形（Java实现）

树上的三角形

时间限制: 2000ms 内存限制: 256mb

描述

有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？

输入

输入数据的第一行包含一个整数 t，表示数据组数。

接下来有 t 组数据，每组数据中：

第一行包含一个整数 n，表示树上节点的个数（从 1 到 n 标号）。

接下来的 n-1 行包含三个整数 a, b, len，表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。

接下来一行包含一个整数 m，表示询问数。

接下来m行每行两个整数 s, t，表示毛毛虫从 s 爬行到了 t，询问这段路程中的树枝/树干是否能拼成三角形。

输出

对于每组数据，先输出一行"case #x:",其中x为数据组数编号，从 1 开始。

接下来对于每个询问输出一行，包含"yes"或“no”，表示是否可以拼成三角形。

数据范围

1 ≤ t ≤ 5

小数据：1 ≤ n ≤ 100, 1 ≤ m ≤ 100, 1 ≤ len ≤ 10000

大数据：1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ len ≤ 1000000000

样例输入

2

5

1 2 5

1 3 20

2 4 30

4 5 15

3 4

3 5

1 4 32

2 3 100

3 5 45

4 5 60

1 4

1 3

样例输出

case #1:

no

yes

case #2:

主要算法：

define results

get t

for 1 to t

get n

for 1 to n-1

get 边

getstruct 边s //构造类树

get m

define result

for 1 to m

get s,e

get s,e 到树根的路劲

get s,e 到树根的路劲的非公共节点

get s,e 间的路劲

get values s,e间路劲的段长度集合

sort(values)

result+=test values//测试是否为三角形

results add result

print results

test 算法

for i=2 to values.length

if values[i-2]+vaules[i-1]>values[i]

return true

return false

程序：

这也是同样了，通过了比赛系统小数据测试，大数据测试未知。

——20130408

ps：

今天早晨数据出来了，这道题的大数据测试时tle，超时。在情理之中。原因见博文《2013编程之美资格赛之大数据测试（java实现）》

——20130409