题意理解

我们有一棵 $n$ 个节点的树，表示 $n$ 个城市和连接它们的道路。

有 $m$ 次语言传播工作，第 $i$ 次传播从 $s_i$ 到 $t_i$（走唯一的最短路径，即树上路径），把第 $i$ 种通用语教给路径上的所有城市。

定义：两个城市 $u$ 和 $v$ 可以开展贸易，当且仅当存在一种通用语 $L$，使得 $u$ 到 $v$ 的路径上的所有城市都会语言 $L$。

换句话说，$u \to v$ 的路径必须完全包含在某一次语言传播的路径中。

我们需要统计有多少个无序对 $(u, v)$（$u < v$）可以开展贸易。

---

问题转化

对于任意两个城市 $u, v$，设 $P_{uv}$ 表示 $u$ 到 $v$ 的路径（按树上的唯一路径）。

条件：存在某次传播 $(s_i, t_i)$，其路径 $Q_i$ 满足 $P_{uv} \subseteq Q_i$。

---

关键观察

1. 路径包含关系
   在树上，一条路径 $P_{uv}$ 被另一条路径 $Q$ 包含，当且仅当 $P_{uv}$ 的两个端点 $u, v$ 都在 $Q$ 上，并且 $P_{uv}$ 是 $Q$ 的一段连续部分。
   更准确地说：
   设 $Q$ 的端点是 $a, b$，$P_{uv}$ 的端点是 $u, v$。
   则 $P_{uv} \subseteq Q$ 当且仅当 $\mathrm{dist}(a, u) + \mathrm{dist}(u, v) + \mathrm{dist}(v, b) = \mathrm{dist}(a, b)$，
   或者 $\mathrm{dist}(a, v) + \mathrm{dist}(v, u) + \mathrm{dist}(u, b) = \mathrm{dist}(a, b)$。
   其实等价于：$u, v$ 都在 $Q$ 上，且 $u, v$ 之间的路径是 $Q$ 的一部分。

2. 等价条件
   在树上，路径 $P_{xy}$ 被路径 $P_{ab}$ 包含的充要条件是：

   $$\mathrm{dist}(a, x) + \mathrm{dist}(x, y) + \mathrm{dist}(y, b) = \mathrm{dist}(a, b) $$

   或者

   $$\mathrm{dist}(a, y) + \mathrm{dist}(y, x) + \mathrm{dist}(x, b) = \mathrm{dist}(a, b) $$

   因为 $\mathrm{dist}(x, y) = \mathrm{dist}(y, x)$，这两个条件其实是对称的，就是 $x, y$ 在 $a \to b$ 路径上且顺序是 $a \to x \to y \to b$（或 $a \to y \to x \to b$）。

3. 简化判断
   更简单的判断：$x, y$ 在路径 $a \to b$ 上，当且仅当：

   $$\mathrm{dist}(a, x) + \mathrm{dist}(x, b) = \mathrm{dist}(a, b) \quad\text{且}\quad \mathrm{dist}(a, y) + \mathrm{dist}(y, b) = \mathrm{dist}(a, b) $$

   并且 $x, y$ 之间的路径完全落在 $a \to b$ 上（自动满足，因为树上两点唯一路径）。

   所以只需检查 $x$ 和 $y$ 是否都在路径 $a \to b$ 上。

---

暴力做法（小数据）

对于 $n, m \le 300$，我们可以：

• 预处理任意两点距离 $\mathrm{dist}(u, v)$（BFS $n$ 次，$O(n^2)$）。
• 对每对 $(u, v)$（$u < v$），检查是否存在一次传播 $(s_i, t_i)$ 使得 $u$ 和 $v$ 都在路径 $s_i \to t_i$ 上。

判断 $u$ 在路径 $s_i \to t_i$ 上的方法：

$$\mathrm{dist}(s_i, u) + \mathrm{dist}(u, t_i) = \mathrm{dist}(s_i, t_i) $$

复杂度：$O(n^2 m)$，对于 $n, m \le 300$ 可过。

---

优化思路

我们需要数有多少点对 $(u, v)$ 满足：存在 $i$ 使得 $u, v$ 都在路径 $s_i \to t_i$ 上。

等价于：点对 $(u, v)$ 如果被某条传播路径同时经过，则贡献 1。

---

转化为：对每个语言路径，数它包含的点对数量

对于一条语言路径 $P$（长度为 $L+1$ 个节点），它包含的点对数量是 $\binom{L+1}{2}$。

但是不同语言路径可能包含相同的点对，直接相加会重复计数。

所以问题变成：给定 $m$ 条树上路径，求它们的点并集的点对数量。
即：令 $S_i$ = 路径 $i$ 上的点集，求 $|\bigcup_{i=1}^m \binom{S_i}{2}|$，其中 $\binom{S_i}{2}$ 表示 $S_i$ 中所有点对。

---

容斥原理

设 $A_{ij}$ 表示事件“点对 $(i, j)$ 被某条路径包含”。

我们要求：

$$\sum_{1 \le i < j \le n} [\exists k: (i,j) \in \mathrm{Path}(s_k, t_k)] $$

这等于：

$$\sum_{1 \le i < j \le n} \left[ \bigvee_{k=1}^m (i,j \in P_k) \right] $$

其中 $P_k$ 是第 $k$ 条路径的点集。

---

另一种思路：对每个点对，判断是否被至少一条路径包含

判断点对 $(u, v)$ 是否被某条路径 $P$ 包含：
路径 $P$ 包含 $(u, v)$ 当且仅当 $P$ 包含 $u$ 和 $v$，且 $u, v$ 在 $P$ 上连续（自动满足）。

所以只需判断 $u, v$ 是否同时在某条路径上。

---

高效算法（$n, m \le 10^5$）

我们可以用 树上差分 + LCA 来标记每条路径覆盖的边或点，但这里需要知道点对是否被同一条路径覆盖。

一个技巧：
对每个点 $x$，记录包含 $x$ 的路径集合（用 bitset 或哈希），然后判断 $u, v$ 是否有公共路径？
但 $m$ 很大时不行。

---

正解思路（参考）

事实上，已知一个方法：

1. 对每个语言路径，把它覆盖的边标记（用该语言的编号）。
2. 点对 $(u, v)$ 可行当且仅当 $u \to v$ 路径上的所有边都被至少同一种语言覆盖。

因为如果 $u \to v$ 路径上所有边都被某条语言路径覆盖，那么整条路径就被它包含。

问题转化为：给 $m$ 条路径，标记边，问有多少点对之间的路径上的边都被至少一个共同语言覆盖。

---

进一步转化

对边考虑：每条边可能被若干种语言覆盖。
点对 $(u, v)$ 可行当且仅当 $u \to v$ 路径上的所有边有一个公共的语言（不一定同一条路径，而是同一种语言编号）。

因为一种语言对应一条路径，如果 $u \to v$ 路径上的边都被语言 $L$ 覆盖，那么 $u \to v$ 路径一定完全在语言 $L$ 的路径内部。

---

具体算法

1. 对每种语言 $i$，它覆盖的边是 $s_i \to t_i$ 路径上的边。
2. 对每条边 $e$，记录覆盖它的语言集合 $L_e$。
3. 我们要求点对 $(u, v)$ 满足：$\bigcap_{e \in P_{uv}} L_e \neq \varnothing$。

也就是说，$u \to v$ 路径上所有边的覆盖语言集合交集非空。

---

实现方法

• 对每种语言，路径 $s_i \to t_i$ 上的边加入语言 $i$（用树上差分，给边打标记）。
• 然后问题变成：有多少点对，路径上的所有边都包含某种共同语言 $x$。

换个角度：对每种语言 $x$，考虑所有被它覆盖的边，这些边形成一条路径（就是 $s_x \to t_x$ 路径）。
那么所有点对 $(u, v)$ 如果完全在这条路径上，就满足条件。

所以又回到：点对 $(u, v)$ 满足它在某条语言路径上。

---

最终算法

我们只需对每条语言路径 $P$，计算它上面的点对数量 $\binom{|P|}{2}$，然后去重。

去重：如果两条语言路径有重叠的点对，只算一次。

这相当于求 $m$ 条路径的点集的并集，然后计算这个并集中有多少点对。

---

去重方法

点对 $(u, v)$ 可能出现在多条路径中，我们只计一次。

我们可以用 二维平面 扫描的方法，但较复杂。
一个简单方法：
对每个点对，它第一次被哪条路径覆盖？很难。

但已知一个 $O(n + m)$ 做法（cf. 类似题目）：
把路径按某种顺序处理，用并查集维护已经覆盖的连续段。

---

简单总结

对于本题 $n, m \le 10^5$，标算可能是：

1. 求出每条路径的节点集合（用 O(1) LCA 可得路径长度）。
2. 用容斥或线段树合并维护覆盖点对去重。

但实现较复杂，这里不展开代码。

---

公式总结

• 两点距离：$\mathrm{dist}(u, v) = \mathrm{depth}[u] + \mathrm{depth}[v] - 2 \times \mathrm{depth}[\mathrm{LCA}(u, v)]$
• 点 $x$ 在路径 $a \to b$ 上：

$$\mathrm{dist}(a, x) + \mathrm{dist}(x, b) = \mathrm{dist}(a, b) $$

• 路径包含点对：路径 $P$ 包含点对 $(u, v)$ 当且仅当 $u, v \in P$。