P5189: 拉力赛-训练套题T12T3

---

【题目描述】

第三题：拉力赛(rally.pas/c/cpp) 车展结束后，游乐园决定举办一次盛大的山道拉力赛，平平和韵韵自然也要来参加大赛。 赛场上共有n个连通的计时点，n-1条赛道（构成了一棵树）。每个计时点的高度都不相同（父结点的高度必然大于子结点），相邻计时点间由赛道相连。由于马力不够，所以韵韵的遥控车只能从高处驶向低处。而且韵韵的车跑完每条赛道都需花费一定的时间。 举办方共拟举办m个赛段的比赛，每次从第u个计时点到第v个计时点，当然其中有不少比赛韵韵的遥控车是不能参加的（因为要上坡）。平平想知道他能参加多少个赛段的比赛，并且想知道他完成这些赛段的总用时。 【输入格式】 第一行两个整数n，m。 接下来n-1行每行3个整数a、b、t。 表示韵韵的遥控车可以花t秒从第a个计时点到第b个计时点。 接下来m行每行2个整数u、v，意义如描述所示。 【输出格式】 第一行输出一个正整数，表示能参加的赛段数。 第二行输出一个正整数，表示总用时。 【输入样例】 6 2 1 2 1 2 4 1 2 5 1 5 6 1 1 3 1 2 6 4 5 【输出样例】 1 2 【提示及范围】 第一个计时点的高度是最高的； u≠v； 对于50％的数据 n≤1000 m≤1000； 对于100％的数据 n≤10000 m≤100000； 答案小于2^64。

【提示】

题目类型~

模拟赛-训练套题 

咻咻~

提交答案 状态 返回