曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6039: 带权树上最长路径

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：15 Solved：5
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

给你一棵n个节点的带边权的有根树，节点标号为1~n，1号节点为根节点。
树上两点u、v间的有且仅有一条路径。这条路径包含的各边边权之和就是路径的长度。
现在要求哪两个点间的路径长度最长。请你输出这个长度。

Input

第一行一个整数n。
以后n行，每行若干个整数。第i行，第一个数为mi，表示节点i的子节点个数。紧接着2*mi个整数，分成mi个二元组，2个整数为一组（j，w），表示节点j是节点i的子节点，且连接节点i、j的边权值为w。保证父节点编号小于子节点。
n≤1000，边权均不超过100

Output

一行一个整数，表示树上最长路长度。

Sample Input Copy 

3
2 2 1 3 1
0
0

Sample Output Copy 

2

HINT

1节点连2节点，边权为1；1节点连3节点，边权为1

Source/Category