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!