A Problem For Fun

A Problem For Fun

Time Limit:50000MS Memory Limit:265536K
Total Submit:7 Accepted:2
Case Time Limit:10000MS

Description

给出一个N个结点的树,每条边有一个正整数权值,定义两个结点的距离为连接这两个结点路径上边权的和。对于每个结点i,它到其他N-1个结点都有一个距 离,将这些距离从小到大排序,输出第K个距离。

Input

输入文件总共N行。第一行有两个正整数N和K。下面N-1行每行描述树的一条边(保证这些边可以构成一棵树),每行三个正整数u、v、w,表示从结点u到 结点v有一条权值为w的边。
输入文件保证:N <= 50000, K < N, u <= N, v <= N, w <= 10000。

Output

输出文件总共N行,每行一个正整数,第i行的数对于结点i的答案。

Sample Input

Sample Output

Source

陶文博

这个题目解法有好多。。真是道好题。。我有时间写个完整一点的解题报告罗列一下解法。。
我写的是边分治。。因为比较好弄。。
首先通过添加辅助点的办法让点的最大度数为3。。
具体的说就是对于每个度数大于3的点。。
比如说度数为d,构造d个点,每个点分到一个边。。同时这d个点用长为0的边连起来。。
然后边分治。。找到分治的边。。
那么一个点出发的所有路径最多出现在LogN个分治中。。
考虑“一个点出发的路径长度<L的有多少个”这样的询问。。
我们可以通过排序的办法在LogN^2回答这个问题。。
然后通过二分来回答K近顶点的话。。
就是LogN^3了。。
N个点就是NLogN^3
好说不好写。。写了9KB+。。
解法2:
这个想法来自twb。。就是dfs一棵树的话。。
用一个数据结构维护树的dfs序列。。
那么一个字树是一个区间。。
注意到我沿着一条边移动。。设从i->j。。
那么j对应的区间到当前点的距离全部降低cost(i->j)
其它的点全部增加cost(i->j)
那么我们要回鹘一个数据结构。。
支持:
给一段数都增加一个值。。
找所有数中的K大。。
这个情况没有办法用神马有效的办法解决。。只能块状了。。
块状的话找K大还是得先二分。。就有个LogN了。。
就是转变成解决询问比一个数小的数有几个这个问题。。
考虑我们把序列分成L块。。
考虑各种复杂度:
为了支持询问我们得给每个块维护一个排过序的数列。。
给一个块部分增加值:
找出那部分,增加,归并,O(L)
给一个块整体增加值:
直接维护一个标记 O(1)
一个块的询问 O(LogL)<O(LogN)(为了方便看成LogN)
所有块的一次询问 (N/L)*LogL< (NLogN)/L
所有块的查询K大 LogN*(NLogN)/L=(NLogN^2)/L
修改一个区间 O(L+N/L) 假设L>N/L。。则为O(L)
我们在dfs的过程中。。
要进行O(N)次询问,O(N)次修改操作。。
所以让这两个操作平衡起来。。
既L=(NLogN^2)/L
解得L=Sqrt(N)LogN
总共就是N*Sqrt(N)LogN了。。
比第一个要好写一点。。速度也差不多。。

4
6
4
7
5
6

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

12 thoughts on “A Problem For Fun

  1. Yesterday, while I was at work, my sister stole my apple ipad and tested to
    see if it can survive a 30 foot drop, just so she can be
    a youtube sensation. My apple ipad is now destroyed and she
    has 83 views. I know this is entirely off topic but I had to share it with someone!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>