Vijos P1460 拉力赛

Vijos P1460 拉力赛

拉力赛

描述

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

格式

输入格式

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

输出格式

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

样例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
提示
第一个计时点的高度是最高的；
u≠v；
对于50％的数据 n≤1000 m≤1000；
对于100％的数据 n≤10000 m≤100000；
答案小于2^64。
来源
f1zsy birdor

分析

该题所说遥控车只能从高度大的向高度小的行驶，而题目又给出了父亲的高度又比儿子的高度大，由此该题目就是寻找u是否为v的祖先（不一定是最近祖先）

而对于树，其先根遍历序根在叶子前面出现，后根遍历序叶子在根前面出现，所以只要v在先根遍历比u出现晚，在后根遍历比u出现早那肯定u是v的祖先

先根遍历后面的与后根遍历前面的重合的必然是根的孩子；

由此可以设置一个时间戳来记录其遍历的时间。时间在dfs过程中计算从根到叶子的时间，即time[叶子]=time[叶子]+time[根]
那么 从u 到 v所花费时间即为 time[v]-time[u]

代码如下

program p1460;
type point=^rec;rec=recorde,v:longint;s:point;end;
var n,m,i:longint;s,e,v:longint;x,y:longint;step:longint;total,cost:qword;vertex:array[1..10000] of point;root_first,root_last:array[1..10000] of longint;time:array[1..10000] of qword;procedure insert(s,e,v:longint);
var p:point;
beginnew(p);p^.e:=e;p^.v:=v;p^.s:=vertex[s];vertex[s]:=p;
end;procedure dfs(head:longint;p:point);
beginwhile p<>nil dobegininc(step);root_first[p^.e]:=step;time[p^.e]:=time[p^.e]+time[head];dfs(p^.e,vertex[p^.e]);inc(step);root_last[p^.e]:=step;p:=p^.s;end;
end;beginassign(input,'D:/input/');reset(input);assign(output,'D:/output/');rewrite(output);readln(n,m);for i:=1 to n-1 dobeginreadln(s,e,v);insert(s,e,v);time[e]:=v;end;time[1]:=0;step:=1;root_first[1]:=0;dfs(1,vertex[1]);root_last[1]:=step+1;for i:=1 to m dobeginreadln(x,y);if (root_first[x]<root_first[y]) and (root_last[x]>root_last[y])thenbegintotal:=total+1;cost:=cost+(time[y]-time[x]);end;end;writeln(total);write(cost);close(input);close(output);
end.

评测结果

测试数据 #0: Accepted, time = 0 ms, mem = 992 KiB, score = 10
测试数据 #1: Accepted, time = 7 ms, mem = 996 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 992 KiB, score = 10
测试数据 #3: Accepted, time = 3 ms, mem = 996 KiB, score = 10
测试数据 #4: Accepted, time = 1 ms, mem = 992 KiB, score = 10
测试数据 #5: Accepted, time = 55 ms, mem = 1080 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 1248 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 1160 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 1136 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 1248 KiB, score = 10
Accepted, time = 281 ms, mem = 1248 KiB, score = 100

总结

要注意数据范围，快被坑死了。。。╮(╯▽╰)╭