Hello, I made a very classic tree problem. I want to get some clean solutions, because my solution seems very complicated. I made this problem on Polygon, but cannot make it public to every one. So I publish this problem here.
I hope you can give me good solutions (maybe by ideone.com / or join my group).
I create a group called "problem sharing" at http://mirror.codeforces.com/group/t0m8sIZmgT. You can join this group to solve this problem.
Given a tree with n vertices and a positive integer D. Vertices are numbered from 1 to n. Each vertex u has a positive weight wu.
For each vertex u, compute ans[u] = max{wv: dist(u, v) = D}. if such vertex v does not exist, ans[u] = - 1.
Where dist(u, v) is length of shortest path between u and v.
First line contains integer n and D. (1 ≤ n ≤ 100000, 1 ≤ D ≤ 100).
Second line contains n integers w1, w2, ..., wn. (1 ≤ wi ≤ 109)
Then (n - 1) lines follow. Each line contains two integer u and v, which means there is an edge (u, v).
Output n intergers in a single line. i-th of them should be ans[i].
5 2
1 3 4 2 5
1 2
2 3
3 4
4 5
4 2 5 3 4
5 2
1 3 7 2 5
1 5
2 5
3 5
4 5
7 7 3 7 -1
