问题2124--tmk找三角

2124: tmk找三角

时间限制: 1 Sec  内存限制: 128 MB
提交: 1140  解决: 250
[状态] [讨论版] [提交] [命题人:]
题目描述

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

输入

第一行输入一个T,表示有多少组样例。

对于每组数据:第一行包含一个整数 N,表示树上节点的个数(从 1 N 标号)。

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

接下来一行包含一个整数 M,表示询问数。

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

输出

对于每组数据,每个询问输出一行,包含"Yes"“No”,表示是否可以拼成三角形。

样例输入 Copy
4
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
样例输出 Copy
No
Yes
No
Yes
来源/分类