【小奇模拟赛2】[bzoj3784]小奇的树

2016年5月22日2,9742

【题目背景】

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

【问题描述】

给定一棵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

 

  • hzy2015年12月28日 下午10:27 回复

    黄学长,链接404了

    #1  
    • hzwer2015年12月28日 下午10:33 回复
      admin

      不存在了QAQ

      #11