注：本题所有边的边权均为,下文将不再提及。 给定一棵个点的树,现在通过以下规则创造一个个点的图 将的点分为组，每组个点，每个点的标号为，表示这是第组第个点。 中存在边当且仅当且边 构造完之后，我们再向其中加入另外的条边，第条边连接点和点。 最后，请你求出点至点的最短路
输入描述:
第一行数字接下来行，每行两个数字，表示树中的一条边接下来行，每行四个数字，表示一条被添加的边接下来一行四个数字。
输出描述:
一行一个数字表示答案，若与不连通则输出
示例1
输入
4 4 3
1 2
1 3
3 4
1 2 2 2
1 3 3 1
2 3 3 2
3 2 3 4
1 2 3 4
备注:
保证答案在int范围内，可能有重边
加载中...