### ChuYuxun's blog

By ChuYuxun, 13 years ago, I was thinking an interesting problem these days, but I can't solve it.

Given an un-rooted tree with N nodes and a number k.
Each edge has distance 1.
Nodes are numbered from 1 to N.

Define :
Dis(i, j) = the distance between node #i & #j in this tree

V[x] : A list, V=dis(1,x), V=dis(2,x) .... v[x-1]=dis(x-1,x), v[x]=dis(x+1,x)....v[n-1]=dis(n,x)

s[x] : sort V[x] in descending order to get s[x]

Ans[x] : the kth element of s[x]

All I need is to output Ans[]

I want a algorithm which runs in O(Nlog^2N) or faster.

Help me to solve this problem, Thanks!  Comments (7)
 maybe your description is incorrect, but in my understanding the problem is very easy. First, we need to find distances from vertex x to each of other nodes. We can use one BFS from x, to find it. then build array v and sort it.BFS - O(n) and sort - O(N log N)
•  .... I want to output ans, ans, ans .... ans[n]
 yes, now i undertand the problem, sorry.
 can you give me a link to this problem on some archive, where i can submit it.i think there is a solution with binary tree, somethink like dfs(Vertex x, BinTree t)the binary tree must contain all distances from x to each of vertices which is not in subtree rooted at x. I can imagine many ways to do such dfs, but i can't decide what complexity it has. I think it can be done efficiently.
•  Sorry, this problem was origined by myself.I tried to use dfs & balanced binary search tree to solve it.We have to add a number (possibly negative) to a consecutive interval, and findout the kth number among all the numbers when we dfs the whole tree.This could be really tough.
•  This may be somehow related: http://acm.timus.ru/problem.aspx?space=1&num=1752
•  It's like the problem when k == 1