问题1023--拉力赛

1023: 拉力赛

时间限制: 1 Sec  内存限制: 128 MB
提交: 229  解决: 118
[提交] [状态] [讨论版] [命题人:]

题目描述

车展结束后,游乐园决定举办一次盛大的山道拉力赛,罗老师自然也要来参加大赛。
赛场上共有n个连通的计时点,n-1条赛道(构成了一棵树)。每个计时点的高度都不相同(父结点的高度必然大于子结点),相邻计时点间由赛道相连。由于马力不够,所以韵韵的遥控车只能从高处驶向低处。而且韵韵的车跑完每条赛道都需花费一定的时间。
举办方共拟举办m个赛段的比赛,每次从第u个计时点到第v个计时点,当然其中有不少比赛韵韵的遥控车是不能参加的(因为要上坡)。平平想知道他能参加多少个赛段的比赛,并且想知道他完成这些赛段的总用时。
赛道皆为单向。
结点1是根节点,最高。

输入

第一行两个整数n,m。
接下来n-1行每行3个整数a、b、t。
表示韵韵的遥控车可以花t秒从第a个计时点到第b个计时点。
接下来m行每行2个整数u、v,意义如描述所示。

输出

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

样例输入 Copy

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

样例输出 Copy

1
2

提示

【数据规模和约定】
输入可能是无向图
u≠v;
答案小于2^63-1。
N<=10000
M<=100000
题解:
使用时间戳判断一个点是否是另一个点的子孙
Dep[i]表示i到跟的距离
如果是的话,只要dep[child]-dep[father]

来源/分类