802J1.md (2529B)
1 Source: https://codeforces.com/problemset/problem/802/J1 2 3 J1. Send the Fool Further! (easy) 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Heidi's friend Jenny is asking Heidi to deliver an important letter to one of their common friends. Since Jenny is Irish, Heidi thinks that this might be a prank. More precisely, she suspects that the message she is asked to deliver states: "Send the fool further!", and upon reading it the recipient will ask Heidi to deliver the same message to yet another friend (that the recipient has in common with Heidi), and so on. 22 23 Heidi believes that her friends want to avoid awkward situations, so she will not be made to visit the same person (including Jenny) twice. She also knows how much it costs to travel between any two of her friends who know each other. She wants to know: what is the maximal amount of money she will waste on travel if it really is a prank? 24 25 Heidi's *n* friends are labeled 0 through *n* - 1, and their network of connections forms a tree. In other words, every two of her friends *a*, *b* know each other, possibly indirectly (there is a sequence of friends starting from *a* and ending on *b* and such that each two consecutive friends in the sequence know each other directly), and there are exactly *n* - 1 pairs of friends who know each other directly. 26 27 Jenny is given the number 0. 28 29 Input 30 31 The first line of the input contains the number of friends *n* (3 ≤ *n* ≤ 100). The next *n* - 1 lines each contain three space-separated integers *u*, *v* and *c* (0 ≤ *u*, *v* ≤ *n* - 1, 1 ≤ *c* ≤ 104), meaning that *u* and *v* are friends (know each other directly) and the cost for travelling between *u* and *v* is *c*. 32 33 It is guaranteed that the social network of the input forms a tree. 34 35 Output 36 37 Output a single integer – the maximum sum of costs. 38 39 Examples 40 41 Input 42 43 ``` 44 4 45 0 1 4 46 0 2 2 47 2 3 3 48 ``` 49 50 Output 51 52 ``` 53 5 54 ``` 55 56 Input 57 58 ``` 59 6 60 1 2 3 61 0 2 100 62 1 4 2 63 0 3 7 64 3 5 10 65 ``` 66 67 Output 68 69 ``` 70 105 71 ``` 72 73 Input 74 75 ``` 76 11 77 1 0 1664 78 2 0 881 79 3 2 4670 80 4 2 1555 81 5 1 1870 82 6 2 1265 83 7 2 288 84 8 7 2266 85 9 2 1536 86 10 6 3378 87 ``` 88 89 Output 90 91 ``` 92 5551 93 ``` 94 95 Note 96 97 In the second example, the worst-case scenario goes like this: Jenny sends Heidi to the friend labeled by number 2 (incurring a cost of 100), then friend 2 sends her to friend 1 (costing Heidi 3), and finally friend 1 relays her to friend 4 (incurring an additional cost of 2).