EAGLE1 - Eagle and Dogs


Eagle (AKA Mohamed Ahmed) lives in a city consists of n intersections connected by n-1 roads, in a way that can go from any intersection to any other intersection moving along some of these roads.

Every day he starts walking in the city following a simple strategy; if he's at some intersection he has to pick one of the roads connected to it at random such that he hasn't walked through it before and walk through it and and if there isn't any, he stops and goes home.

His only problem is that he's afraid of dogs. He doesn't even like seeing dogs. So he's wondering in the worst scenario, how many dogs he'll have to see during his walk until he stops if he starts walking at some intersection. Can you help him?

Input

The input starts with an integer T (1 <= T <= 10), the number of test cases. following T blocks describing each test case.

Each block starts with a line containing an integer n (2 <= n <= 105), the number of intersections in the city. Intersections are numbers 1 through n.

Followed by n-1 lines each containing integers u, v, (1 <= u, v <= n) and d (1 <= d <= 109), the numbers of intersections at the end of this road and the number od dogs Eagle will see walking in this road.

Output

For each test case print a line containing n integers, the ith integer represents the maximum number of dogs Eagle might see if he starts his walk at intersection i.

Example

Input:
1
4
1 2 3
3 2 4
3 4 5 Output: 12 9 7 12

hide comments
demon_coder123: 2023-05-29 12:52:36

can anyone please post a link for the explanation of this problem solution using dp PLEASE.

nahid_180103: 2023-05-04 21:41:41

I call dfs for 4 times....But AC!!!

amit_20je0117: 2022-10-28 21:44:41

Rerooting technique for DP on trees !!
Ac in one go.
Need to call dfs only two times .
Overall time complexity O(N).

Last edit: 2022-10-28 21:46:05
sankalp_7: 2022-10-17 20:07:16

Nice "DP on trees" question ;)

l3vel: 2022-01-23 05:54:15

For all those getting TLE, You will have to use dp along with dfs approach
if you dont know dp, and want to be sure of your dfs implementation, see whether you solution passes through this tc,

input ->
1
8
1 2 1
2 3 100
2 4 2
4 5 5
4 6 3
6 7 6
6 8 4

output->
101 100 111 102 107 105 111 109

hsn_kei: 2021-11-25 04:45:41

you can call dfs 5 or 6 time
dont worry about tle :)

teslum_369: 2021-10-23 15:02:48

You can use the DFS three times.

Hint: Consider the diameter of the tree (depending on the number of dogs, not number of streets!)

princemishra: 2021-06-26 07:23:04

dp on trees question
example test case:

1
6
1 2 3
1 3 5
2 4 15
4 5 120
3 6 12

op:
138 135 143 120 155 155

cryp_bipul17: 2021-05-11 07:41:23

I am trying to run two dfs one from the beginning and another from end and counting the number of dogs in each node and finding the maximum of the two dfs but getting WA can anyone please tell is my approach correct

sshubham_26: 2021-04-28 17:05:09

i have called dfs two times only


Added by:eagle93
Date:2015-06-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY