/ WHOJ / 题库 /

拉力赛

拉力赛

测试数据来自 system/1460

题目描述

车展结束后,游乐园决定举办一次盛大的山道拉力赛,平平和韵韵自然也要来参加大赛。

赛场上共有 \(n\) 个连通的计时点,\(n-1\) 条赛道(构成了一棵树)。每个计时点的高度都不相同(父结点的高度必然大于子结点),相邻计时点间由赛道相连。由于马力不够,所以韵韵的遥控车只能从高处驶向低处。而且韵韵的车跑完每条赛道都需花费一定的时间。

举办方共拟举办 \(m\) 个赛段的比赛,每次从第 \(u\) 个计时点到第 \(v\) 个计时点,当然其中有不少比赛韵韵的遥控车是不能参加的(因为要上坡)。平平想知道他能参加多少个赛段的比赛,并且想知道他完成这些赛段的总用时。

格式

输入格式

第一行两个整数 \(n,m\)。

接下来 \(n-1\) 行每行 \(3\) 个整数 \(a、b、t\)。

表示韵韵的遥控车可以花 \(t\) 秒从第 \(a\) 个计时点到第 \(b\) 个计时点。

接下来 \(m\) 行每行 \(2\) 个整数 \(u、v\),意义如描述所示。

输出格式

第一行输出一个正整数,表示能参加的赛段数。

第二行输出一个正整数,表示总用时。答案小于 \(2^{64}\)。

样例1

样例输入1

6 2
1 2 1
2 4 1
2 5 1
5 6 1
1 3 1
2 6
4 5

样例输出1

1
2

限制

时间:\(1s\) 空间:\(64M\)

对于 \(50\%\) 的数据 \(n<=1000,m<=1000\);

对于 \(100\%\) 的数据 \(t,n<=10000,m<=100000\);

来源

地址:\(zloj,J2021\)域
作者:\(jialiang2509\)
模拟赛 \(T2\)