首页 > 试题广场 >

Longest Path

[编程题]Longest Path
In ICPCCamp, there are n cities numbered with 1, 2, ..., n and (n - 1) bidirectional roads. The i-th road has color ci and connects cities ai and bi. It is guaranteed that cities can reach each other.
Going from city u to city v via the unique shortest path, one may pass roads e1, e2, ..., ek in order. Bobo denotes as d(u, v).
For each city u, find out .

输入描述:
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains an integer n.
The i-th of the following (n - 1) lines contains 3 integers ai, bi, ci.


输出描述:
For each test case, print n integers f1, f2, ..., fn.
示例1

输入

2
1 2 1
4
1 2 1
2 3 2
3 4 1

输出

0
0
2
1
1
2

备注:
* 1 ≤ n ≤ 105
* 1 ≤ ai, bi ≤ n
* 1 ≤ ci ≤ 105
* The sum of n does not exceed 106.
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

dp的优化
难度：
0条回答 8浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Longest Path

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号