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[1]=dis(1,x), V[2]=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!

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[1]=dis(1,x), V[2]=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!

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[1], ans[2], ans[3] .... 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.

It's like the problem when k == 1