「小奇模拟赛2」[BZOJ3784] 小奇的树

2016年5月22日7,5032

「题目背景」

小奇在研究树时,遇到了一个难题。

「问题描述」

给定一棵n个节点的树,求前m条最长路径的长度。

「输入格式」

第1行2个整数n,m。

接下来n-1行,每行3个整数u,v,l,表示u,v之间有一条长度为l的边。

「输出格式」

m行如题,从大到小输出。

「样例输入」

4 2

1 2 1

1 3 2

1 4 3

「样例输出」

5

4

「数据范围」

序号

n

m

数据类型

1

10

3

暴力

2

233

23333

暴力

3

2000

300000

暴力

4

2000

300000

暴力

5

50000

1

随机生成

6

7798

17798

随机生成

7

7798

27798

随机生成

8

7798

37798

随机生成

9

50000

300000

1-n顺序输入的链

10

50000

300000

以1为根的菊花图

所有的数据及答案均为不超过int范围的正整数

「题解」

这题是bzoj3784的弱化版

原题是给定一棵n个点的树(n <= 50000),求出树上距离前m大的路径长度(m <= 300000)。

对于40%的数据,bfs加堆或者排序咯。。。

随机生成的数据,可以用点分治加上一些优先队列的奇技淫巧,然而这不是重点

还是来说说原题吧QAQ

1.二分+点分治

二分m大的路径长度,得到下界以后显然是一个nlog^2的经典点分治,加上二分的log,显然比较虚。但是点分治中有一个log是sort需要的,我们就可以先一次点分治把sort的结果用vector存下来,这样的话就能把总复杂度降为nlog^2,得到m大的路径最后一次点分治暴力统计路径。

2.点分治+堆

考虑超级钢琴的做法,点分治时依次扫每棵子树,若将当前子树内的点作为路径的一个端点,另一个端点可以落在一个点分治序列的区间内(之前扫过的子树),这样得出一个长度为nlogn的点分治序列,加上每个点所对应的区间,然后就完全转为超级钢琴的问题了

暴力40

解法2

 

avatar
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
hzwerhzy Recent comment authors
  Subscribe  
提醒
hzy
hzy

黄学长,链接404了