C. Two Trees
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A tree is a set of $$$N$$$ nodes and $$$N-1$$$ undirected edges. Each edge connects two distinct nodes, and between any two nodes there is a unique path that doesn't repeat edges. Further, each edge has an integer edge weight.

You are given two trees, tree X and tree Y. In both these trees, there are $$$N$$$ nodes numbered from $$$1$$$ to $$$N$$$ and $$$N-1$$$ edges numbered from $$$1$$$ to $$$N-1$$$, but the specific edge structures and edge weights of tree X and tree Y may differ.

In tree X, the $$$i$$$-th edge connects nodes $$$A_i$$$ and $$$B_i$$$ and has weight $$$C_i$$$.

In tree Y, the $$$j$$$-th edge connects nodes $$$U_j$$$ and $$$V_j$$$ and has weight $$$W_j$$$.

For some two nodes $$$p$$$ and $$$q$$$ such that $$$1 \leq p \lt q \leq N$$$, $$$\text{cost}_X(p, q)$$$ is defined as the largest edge weight that occurs on the unique path between $$$p$$$ and $$$q$$$ in tree X. Similarly, $$$\text{cost}_Y(p, q)$$$ is defined as the largest edge weight that occurs on the unique path between $$$p$$$ and $$$q$$$ in tree Y.

You are asked to find the number of pairs of nodes $$$(p, q)$$$ such that $$$1 \leq p \lt q \leq N$$$ and $$$\text{cost}_X(p, q) \leq \text{cost}_Y(p, q)$$$. (In total, there are $$$\frac{N(N-1)}{2}$$$ pairs of nodes $$$(p, q)$$$ such that $$$1 \leq p \lt q \leq N$$$.)

Input

The first line of input contains a single integer $$$N$$$, the number of nodes.

The next $$$N-1$$$ lines describe tree X. The $$$i$$$-th of these lines contains three integers, $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$.

The next $$$N-1$$$ lines describe tree Y. The $$$j$$$-th of these lines contains three integers, $$$U_j$$$, $$$V_j$$$, and $$$W_j$$$.

Output

You should print a single integer, the number of pairs of nodes $$$(p, q)$$$ such that $$$1 \leq p \lt q \leq N$$$ and $$$\text{cost}_X(p, q) \leq \text{cost}_Y(p, q)$$$.

Scoring

The test data for this problem is divided into multiple subtasks. In order to pass a subtask, your submitted program must solve every test case within that subtask correctly and within the time and memory limits.

You will be awarded the points allocated to a subtask if at least one submission you make during the contest passes that subtask. You do not need to combine your solutions for multiple subtasks into a single submission.

Please keep in mind that the subtasks are not necessarily arranged in increasing order of difficulty. We encourage you to try as many subtasks as possible.

Constraints

In all test data, it is guaranteed that:

  • $$$1 \leq N \leq 100\:000$$$.

  • For all $$$i$$$ such that $$$1 \leq i \leq N-1$$$:
    • $$$1 \leq A_i \leq N$$$.
    • $$$1 \leq B_i \leq N$$$.
    • $$$A_i \neq B_i$$$.
    • $$$1 \leq C_i \leq 1\:000\:000\:000$$$.
  • For all $$$j$$$ such that $$$1 \leq j \leq N-1$$$:
    • $$$1 \leq U_j \leq N$$$.
    • $$$1 \leq V_j \leq N$$$.
    • $$$U_j \neq V_j$$$.
    • $$$1 \leq W_j \leq 1\:000\:000\:000$$$.

Please be aware that the output for this problem may not fit in 32-bit integers. You may need to use 64-bit integers in your computations.

Notation

The following notation is used to describe the subtasks:

  • The Lines constraint is present in subtasks 1, 4 and 5. This means that for all $$$i$$$ such that $$$1 \leq i \leq N-1$$$, the following conditions hold:
    • $$$A_i = i$$$.
    • $$$B_i = i+1$$$.
    • $$$U_i = i$$$.
    • $$$V_i = i+1$$$.

  • The constraint $$$C_1 \leq C_2 \leq ... \leq C_{N-1}$$$ is present in subtasks 1, 4, 6 and 7. This means that for each $$$i$$$ such that $$$1 \leq i \leq N-2$$$, $$$C_i \leq C_{i+1}$$$ holds.

  • The constraint $$$W_1 \leq W_2 \leq ... \leq W_{N-1}$$$ is present in subtasks 1, 4 and 7. This means that for each $$$j$$$ such that $$$1 \leq j \leq N-2$$$, $$$W_j \leq W_{j+1}$$$ holds.

  • The constraint $$$(A_i, B_i) = (U_i, V_i)$$$ is present in subtasks 6 and 7. This means that for all $$$i$$$ such that $$$1 \leq i \leq N-1$$$, $$$A_i = U_i$$$ and $$$B_i = V_i$$$. In other words, tree X and tree Y have the same $$$N-1$$$ edges (but may have differing edge weights).

Subtasks

  • Subtask 1 (4 points) $$$N \leq 200$$$, Lines, $$$C_1 \leq C_2 \leq ... \leq C_{N-1}$$$, $$$W_1 \leq W_2 \leq ... \leq W_{N-1}$$$.
  • Subtask 2 (5 points) $$$N \leq 200$$$.
  • Subtask 3 (7 points) $$$N \leq 2\:000$$$.
  • Subtask 4 (8 points) Lines, $$$C_1 \leq C_2 \leq ... \leq C_{N-1}$$$, $$$W_1 \leq W_2 \leq ... \leq W_{N-1}$$$.
  • Subtask 5 (15 points) Lines
  • Subtask 6 (10 points) $$$(A_i, B_i) = (U_i, V_i)$$$, $$$C_1 \leq C_2 \leq ... \leq C_{N-1}$$$, all $$$W_i$$$ are equal.
  • Subtask 7 (15 points) $$$(A_i, B_i) = (U_i, V_i)$$$, $$$C_1 \leq C_2 \leq ... \leq C_{N-1}$$$, $$$W_1 \leq W_2 \leq ... \leq W_{N-1}$$$.
  • Subtask 8 (36 points) No further constraints.
Examples
Input
4
1 2 2
2 3 3
3 4 9
1 2 2
2 3 6
3 4 8
Output
3
Input
5
1 2 8
2 3 6
3 4 2
4 5 7
1 2 10
2 3 4
3 4 7
4 5 5
Output
8
Input
5
1 4 6
2 3 8
1 2 9
2 5 10
1 4 8
2 3 8
1 2 8
2 5 8
Output
2
Input
6
1 2 2
2 4 6
3 2 8
4 5 8
1 6 10
1 2 3
2 4 5
3 2 5
4 5 9
1 6 11
Output
10
Input
8
1 2 6
2 3 6
1 4 10
2 5 7
4 6 7
3 7 1
5 8 4
1 2 2
1 3 6
1 4 2
4 5 9
1 6 2
5 7 1
7 8 1
Output
11
Note

In the first sample :

  • Consider the pair $$$(p, q) = (1, 3)$$$. In tree $$$X$$$, there are $$$2$$$ edges between $$$1$$$ and $$$3$$$, them being the edge connecting nodes $$$1$$$ and $$$2$$$ with weight $$$2$$$ and the edge connecting nodes $$$2$$$ and $$$3$$$ with weight $$$3$$$. Thus, the maximum weight is $$$3$$$, and hence, $$$\text{cost}_X(1, 3) = 3$$$. Similarly, $$$\text{cost}_Y(1, 3) = 6$$$. Clearly, $$$\text{cost}_X(1, 3) \le \text{cost}_Y(1, 3)$$$, and hence we will count this pair.
  • Consider the pair $$$(p, q) = (2, 4)$$$. $$$\text{cost}_X(2, 4) = 9$$$ and $$$\text{cost}_Y(2, 4) = 8$$$. Thus, we will not count this pair as $$$\text{cost}_X(2, 4) \gt \text{cost}_Y(2, 4)$$$.

We can show that the pairs $$$(p, q) = (1, 2), (2, 3), (1, 3)$$$ all satisfy $$$\text{cost}_X(p, q) \leq \text{cost}_Y(p, q)$$$ while the other $$$3$$$ pairs do not. Hence, the answer is $$$3$$$.

Sample $$$1$$$ is valid for Subtasks 1, 2, 3, 4, 5, 7, 8.

Sample $$$2$$$ is valid for Subtasks 2, 3, 5, 8.

Sample $$$3$$$ is valid for Subtasks 2, 3, 6, 7, 8.

Sample $$$4$$$ is valid for Subtasks 2, 3, 7, 8.

Sample $$$5$$$ is valid for Subtasks 2, 3, 8.