← 返回题目列表

Codeforces · 1797/F

F. 李华与Path

中文机器翻译题面 查看原题

Li Hua 有一个由 $$$n$$$ 个顶点和 $$$n-1$$$ 个边组成的树。顶点编号从 $$$1$$$ 到 $$$n$$$。

如果以下两个陈述之一为真,则一对顶点 $$$(u,v)$$$ ($$$u < v$$$) 被认为是可爱的:

- $$$u$$$ 是路径 $$$(u,v)$$$ 上所有顶点中索引最小的顶点。
- $$$v$$$ 是路径 $$$(u,v)$$$ 上所有顶点中索引最大的顶点。

将有 $$$m$$$ 次操作。在每次操作中,他决定一个整数$$$k_j$$$,然后将编号为$$$n+j$$$的顶点插入到树中,并与编号为$$$k_j$$$的顶点连接。

他想计算手术前和每次手术后可爱对的数量。

假设你是李华,请解决这个问题。

输入

第一行包含单个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 树中的顶点数。

接下来的 $$$n-1$$$ 行包含树的边缘。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$; $$$u_i\ne v_i$$$) — 相应的边。给定的边形成一棵树。

下一行包含单个整数 $$$m$$$ ($$$1\le m\le 2\cdot 10^5$$$) — 操作数。

接下来的 $$$m$$$ 行包含操作 - 每行一个操作。第 $$$j$$$ 操作包含一个整数 $$$k_j$$$ ($$$1\le k_j < n+j$$$) — 一个顶点。

输出

打印 $$$m+1$$$ 整数 — 操作之前和每次操作之后可爱对的数量。

示例

输入 #1

7
2 1
1 3
1 4
4 6
4 7
6 5
2
5
6

输出 #1

11
15
19

注意

初始树如下图所示:

有 $$$11$$$ 可爱对 — $$$(1,5),(2,3),(2,4),(2,6),(2,7),(3,4),(3,6),(3,7),(4,5),(5,7),(6,7)$$$。

同样,我们可以在每次操作后计算可爱的对,结果是$$$15$$$和$$$19$$$。