核心思路

1. 问题转化

对于每个查询 $Q_i$（$s_i$ 个节点），需要标记这些节点在树上的最小连通子图中的所有边。

关键性质：
在树中，给定点集 $S$，其最小连通子图的边集 = 这些点在树上的斯坦纳树的边集 = 这些点两两之间路径的并集。

更高效的做法：

• 将 $S$ 中的点按 DFS 序 排序。
• 然后连接 $S[1] \leftrightarrow S[2] \leftrightarrow \dots \leftrightarrow S[t]$ 以及 $S[t] \leftrightarrow S[1]$ 形成一个环。
• 这个环上的每条边恰好被经过 2 次（除了虚边），而斯坦纳树的每条边恰好被经过 2 次。
• 因此，如果我们给环上的实边（树上实际存在的边）增加 1 的计数，那么斯坦纳树中的每条边计数 +2，不在斯坦纳树中的边计数不变。

---

2. 树上差分公式

设：

• $\text{LCA}(u,v)$ 表示 $u$ 和 $v$ 的最近公共祖先。
• $\text{depth}[x]$ 表示节点 $x$ 的深度。
• $\text{parent}[x][k]$ 表示 $x$ 的 $2^k$ 级祖先。

对于路径 $u \to v$，我们做树上边差分：

• 定义 $d[x]$ 表示节点 $x$ 到其父节点的边的标记增量。
• 对路径 $u \to v$ 上的所有边加 1：$$d[u] \leftarrow d[u] + 1,\quad d[v] \leftarrow d[v] + 1,\quad d[\text{LCA}(u,v)] \leftarrow d[\text{LCA}(u,v)] - 2 $$
• 最后 DFS 一遍，$cnt_e = \sum_{v \in \text{children}(u)} d[v]$，其中 $cnt_e$ 是 $u$ 到父节点的边的覆盖次数。

---

3. 对每个查询的处理

对查询 $S = \{a_1, a_2, \dots, a_t\}$（$t = s_i$）：

1. 将 $S$ 按 DFS 序排序。
2. 对 $j = 1 \dots t$，将路径 $(a_j, a_{j+1})$ 进行边差分（$a_{t+1} = a_1$）。
3. 这样，斯坦纳树中的每条边被统计 $2$ 次，非斯坦纳树边统计 $0$ 次。

公式化：

$$\forall j \in [1, t],\quad \text{updatePath}(a_j, a_{j+1}) \text{ 加 1} $$

其中 $\text{updatePath}(u,v)$ 用差分：

$$d[u] += 1,\quad d[v] += 1,\quad d[\text{LCA}(u,v)] -= 2 $$

---

4. 最终计数

对所有查询执行完毕后，做一次 DFS 统计每条边的实际覆盖次数：

$$\text{cnt}[u] = \sum_{v \in \text{children}(u)} \text{cnt}[v] + d[u] $$

这里 $\text{cnt}[u]$ 表示 $u$ 到父节点的边的覆盖次数。

注意：根节点没有父边，忽略。

---

5. 输出结果

遍历 $n-1$ 条边，如果 $\text{cnt}[u] \ge 2k$（因为每条查询中斯坦纳树的边被 +2），则这条边满足条件。

最终条件：

$$\text{cnt}[e] \ge 2k$$

输出所有满足条件的边的编号（升序）。

---

算法步骤

1. 读入树，DFS 预处理深度、父节点、DFS 序。
2. 预处理 LCA（树上倍增）。
3. 对每个查询：
   • 读入 $s_i$ 个点。
   • 按 DFS 序排序。
   • 对环上相邻点对（包括首尾）做路径差分（+1）。
4. 全局 DFS 计算最终边的覆盖次数。
5. 筛选 $\text{cnt}[e] \ge 2k$ 的边，输出。

---

时间复杂度

• 预处理 LCA：$O(n \log n)$
• 每个查询排序：$O(s_i \log s_i)$，总 $O(S \log n)$
• 差分操作：$O(\log n)$ 每次 LCA，总 $O(S \log n)$
• 统计答案 DFS：$O(n)$

总复杂度 $O(n \log n + S \log n)$，可过。

---

示例验证

用题目样例验证：

树：

1-3
2-3
3-4
6-4
4-5

查询：

1. S1 = {1,3,2,5} → 排序后 {1,2,3,5}，环：1-2, 2-3, 3-5, 5-1
2. S2 = {6,3} → 排序后 {3,6}，环：3-6, 6-3
3. S3 = {3,2} → 排序后 {2,3}，环：2-3, 3-2

差分后统计：

• 边 2 (2-3): +2 (S1) +0 (S2) +2 (S3) = 4 ≥ 2×2=4 ✓
• 边 3 (3-4): +2 (S1) +2 (S2) +0 = 4 ≥ 4 ✓
• 其他边不满足。

输出：

2
2 3

与样例一致。

---