CF1797F.Li Hua and Path
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Li Hua has a tree of n vertices and n−1 edges. The vertices are numbered from 1 to n .
A pair of vertices (u,v) ( u<v ) is considered cute if exactly one of the following two statements is true:
- u is the vertex with the minimum index among all vertices on the path (u,v) .
- v is the vertex with the maximum index among all vertices on the path (u,v) .
There will be m operations. In each operation, he decides an integer kj , then inserts a vertex numbered n+j to the tree, connecting with the vertex numbered kj .
He wants to calculate the number of cute pairs before operations and after each operation.
Suppose you were Li Hua, please solve this problem.
输入格式
The first line contains the single integer n ( 2≤n≤2⋅105 ) — the number of vertices in the tree.
Next n−1 lines contain the edges of the tree. The i -th line contains two integers ui and vi ( 1≤ui,vi≤n ; ui=vi ) — the corresponding edge. The given edges form a tree.
The next line contains the single integer m ( 1≤m≤2⋅105 ) — the number of operations.
Next m lines contain operations — one operation per line. The j -th operation contains one integer kj ( 1≤kj<n+j ) — a vertex.
输出格式
Print m+1 integers — the number of cute pairs before operations and after each operation.
输入输出样例
输入#1
7 2 1 1 3 1 4 4 6 4 7 6 5 2 5 6
输出#1
11 15 19
说明/提示
The initial tree is shown in the following picture:
There are 11 cute pairs — (1,5),(2,3),(2,4),(2,6),(2,7),(3,4),(3,6),(3,7),(4,5),(5,7),(6,7) .
Similarly, we can count the cute pairs after each operation and the result is 15 and 19 .