Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Do You Know Tree ?

By RamprosadG · Limits 2s, 512 MB

“Stay at least one metre distance from others.”

Corona has affected the World as well as Bangladesh. So the Government of Bangladesh has requested the people to stay home. Alice and Bob are now staying home. They are free because of home quarantine. So they hit upon plan for doing interesting something. Bob has got a plan. He told Alice “I will give you a task and you have to complete the task. If you can complete the task, I will give you prize otherwise you give me prize”. Alice agreed with Bob.

The task is simple and it is explained below -

You are given a Tree With N nodes and N - 1 weighted edge. You are given Q queries. In each query you are given a node X and you have to choose two nodes whose distance is as long as possible and in the shortest path of these nodes the given node X must exist. You have to print this distance.

The distance between two nodes is the summation of edge’s weights in the shortest path between these nodes.

Input

The first line contains an integer N(1 ≤ N ≤ 1000000), the number of node in the tree.
Next N - 1 line contains three integer U, V, W(1 ≤ U, V ≤ N, 1 ≤ W ≤ 1000000000), an edge between U and V whose weight is W.
Next Line contains an integer Q(1 ≤ Q ≤ 1000000), the number of query.
Next Q lines contain an integer X(1 ≤ X ≤ N), the given node.

Output

For each query you have to print this distance.

Sample

InputOutput
5
1 2 4
1 3 2
2 4 10
2 5 8
2
1
5
16
18

Discussion

Statistics


80% Solution Ratio

skmonirEarliest, 1M ago

prodip_bsmrstuFastest, 0.1s

prodip_bsmrstuLightest, 20 MB

samnoon_baiustShortest, 1495B

Submit

Login to submit