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