P5327 [ZJOI2019] Language

Jiutiao Keliang is a girl who likes patterns. By this pattern, the second problem should be related to data structures. In a distant kingdom, there are $n$ cities. There are $n - 1$ bidirectional roads between the cities, and these roads guarantee that any two cities can reach each other directly or indirectly. In ancient times, these $n$ cities were at war with each other. In a highly isolated environment, each city developed its own language. After the kingdom was unified, language barriers greatly hindered the kingdom’s development. To improve this, the king ordered the design of $m$ common languages and carried out $m$ language unification operations. In the $i$-th operation, a minister started from city $s_i$, walked to $t_i$ along the shortest path, and taught every city on the way (including $s_i$ and $t_i$) to use the $i$-th common language. Once there is a shared language, cities can conduct trade. Two cities $u_i, v_i$ can conduct trade if and only if there exists a common language $L$ such that every city on the shortest path from $u_i$ to $v_i$ (including $u_i$ and $v_i$) can use $L$. To measure the effect of the language unification operations, the king wants you to compute how many pairs of cities $(u, v)$ with $u < v$ can conduct trade.

The first line contains two positive integers $n, m$, representing the number of cities and the number of common languages. The next $n - 1$ lines each contain two integers $x_i, y_i$ ($1 \le x_i, y_i \le n$), indicating a road connecting cities $x_i$ and $y_i$. The next $m$ lines each contain two integers $s_i, t_i$ ($1 \le s_i, t_i \le n$), indicating one language promotion operation.

Output one line with one integer, representing the number of pairs of cities that can conduct trade.

#### Sample Explanation The pairs of cities that can conduct trade are $(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5)$. #### Constraints |Test Point|$n$|$m$|Other Constraints| |:-:|:-:|:-:|:-:| |$1,2$|$\le 300$|$\le 300$|None| |$3,4$|$\le 5\times 10^3$|$\le 5\times 10^3$|None| |$5,6$|$\le 10^5$|$\le 10^5$|$y_i=x_i+1$| |$7\sim 10$|$\le 10^5$|$\le 10^5$|None| For $100\%$ of the testdata, $1 \le x_i, y_i, s_i, t_i \le n\leq 10 ^ 5$, $1\leq m\leq 10 ^ 5$, and $x_i\neq y_i$. Translated by ChatGPT 5