问题2124--tmk找三角

2124: tmk找三角

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

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

输入

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

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

接下来的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
来源/分类