Back to School '17: Hot and Cold

View as PDF

Submit solution


Points:20 (partial)
Time limit:5.0s
Memory limit:256M
Author:

Problem type

You are overseeing a game of Hot and Cold on an unweighted bidirectional tree with N nodes (numbered 1 to N). In this game, you are the leader and there are S seekers, each playing their own individual game. This means that the game of one seeker does not impact the game of any other.

Each seeker and their game is characterized by three integers, a_s, b_s and t_s. The target node, t_s, is the node that they are trying to find. The seeker will then traverse each node on the straight path from a_s to b_s and ask Hot or Cold? at each one. You will respond with a number, the distance from that node to the target.

After answering all these questions, you want to know the sum of answers to each node. If no question has been asked about the node, then the answer is 0.

Input Specification

The first line contains two integers, N S.

The next N-1 lines contain two integers, x y, denoting an edge exists between x \leftrightarrow y.

The next S lines contain three integers, a_s b_s t_s.

Constraints

1 \le N, S \le 10^5

1 \le a_s, b_s, t_s \le N

There are 4 subtasks worth \{15\%, 15\%, 35\%, 35\%\}.

Subtask 1 & 2 [15% + 15% = 30%]

1 \le N, S \le 100

Subtask 1 & 3 [15% + 35% = 50%]

The target t_n is always 1 (t_n = 1, n \in N)

Output Specification

Print N integers. The n^\text{th} integer being the sum of answers to queries about node n. Note that answers may not fit in a 32-bit signed int.

Sample Input 1

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

Sample Output 1

0 3 2 4 2

Explanation for Sample Input

Sample Input 2 (not in pretests)

6 2
3 4
2 5
6 4
5 4
1 2
6 2 6
5 1 2

Sample Output 2

1 3 0 1 3 0

Comments

There are no comments at the moment.