## An Animal Contest 6 P6 - Generous Grizzly Gift Giving

View as PDF

Points: 35 (partial)
Time limit: 4.0s
Memory limit: 256M

Author:
Problem type

Kyriakos Grizzly is planning a meetup with his grizzly friends! The grizzlies are numbered from to (Kyriakos is grizzly ), and the grizzly lives in city . Their plan is to meet up in city where Kyriakos lives. Being smart grizzlies, they will each take the shortest path to city along the network of roads that connects the cities. As a result, the roads that they will use form a tree with edges. After arriving at city , a grizzly will wait for all other grizzlies that will pass through city , so that they can travel together to the next cities.

Being generous as well as smart, when two grizzlies meet for the first time, they will both buy each other a gift from the city in which they met. By the time that all grizzlies have met in city , they should have each received gifts, one from each of the other grizzlies. A gift from city has two properties: a price and a quality . A grizzly's confusion value will be the number of pairs of gifts that he received such that the first gift is from city and the second is from city and and .

Kyriakos would like you to find the total confusion value among the grizzlies if they all attended the meetup. However, he also expects one or two grizzlies to cancel on their plans (they will not attend the meetup). Therefore, he will ask you an additional questions. There will be two types of questions:

• 1 v If grizzly decides to cancel, what would be the total confusion value among the remaining grizzlies attending the meetup?
• 2 u v If grizzlies and decide to cancel, what would be the total confusion value among the remaining grizzlies attending the meetup?

#### Constraints

All are distinct.

All are distinct.

For all questions, .

For type 2 questions, and .

All questions are of type 1.

#### Input Specification

The first line will contain two space-separated integers, and .

The following lines will contain two space-separated integers each, and .

The following lines will contain two space-separated integers each, and , denoting an edge in the tree.

The following lines each describe a question.

#### Output Specification

Output one line containing the total confusion value among all grizzlies if they all attended the meetup.

Output an additional lines containing the answers for each of the questions.

#### Sample Input 1

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

#### Sample Output 1

6

#### Sample Input 2

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

#### Sample Output 2

12
4
4
6
4
6

#### Sample Input 3

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

#### Sample Output 3

12
2
2
0
2
2