## Back to School '17: Hot and Cold

View as PDF

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 nodes (numbered to ). In this game, you are the leader and there are 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, , and . The target node, , is the node that they are trying to find. The seeker will then traverse each node on the straight path from to 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 .

#### Input Specification

The first line contains two integers, .

The next lines contain two integers, , denoting an edge exists between .

The next lines contain three integers, .

#### Constraints

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

The target is always 1 ()

#### Output Specification

Print integers. The integer being the sum of answers to queries about node . 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

#### 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