当前位置:首页 > 差分 > 正文
SSOJ2594公交线路统计
2269+

题目大意:n个城市有n-1条道路相连(一棵树),有m条公交线路(都是两个城市之间的最短路),请问每条道路上分别有多少条公交线路?

输入

第一行:2个整数n和m
第二行:n-1个整数表示城市编号,第i个整数ai表示城市i+1到ai有一条道路,其中ai父亲结点,i+1是儿子结点
接下来m行,每行2个整数表示城市a和b有一条公交线路

输出

输出n-1行,每行3个整数,第i行表示i+1到他父亲结点的道路有多少条公交线路

样例输入

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

样例输出

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

提示

n不超过10万,m不超过50万

解题思路

差分可以让区间修改转化成单点修改,如城市a和城市b有一条公交线路,a和b的公共祖先的c,那么我们可以在点a标记+1(根结点到a所有路径都+1),在点c标记-1(根结点到c所有路径都-1),这样就相当于a到c之间的路径全部+1,因为c以上的由于+1和-1抵消,并没有增加公交线路(b到c之间也是如此)。打完标记后,自下而上把儿子结点的标记累加到父亲结点,这样每个结点到其父亲结点道路上的公交线路就统计出来了。

程序实现

树链剖分求LCA代码:

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ2594公交线路统计:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!