A14756 | Tree Queries
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given a tree consisting of $n$ vertices. Recall that a tree is an undirected connected acyclic graph. The given tree is rooted at the vertex $1$ .
You have to process $q$ queries. In each query, you are given a vertex of the tree $v$ and an integer $k$ .
To process a query, you may delete any vertices from the tree in any order, except for the root and the vertex $v$ . When a vertex is deleted, its children become the children of its parent. You have to process a query in such a way that maximizes the value of $c(v) - m \cdot k$ (where $c(v)$ is the resulting number of children of the vertex $v$ , and $m$ is the number of vertices you have deleted). Print the maximum possible value you can obtain.
The queries are independent: the changes you make to the tree while processing a query don't affect the tree in other queries.
You have to process $q$ queries. In each query, you are given a vertex of the tree $v$ and an integer $k$ .
To process a query, you may delete any vertices from the tree in any order, except for the root and the vertex $v$ . When a vertex is deleted, its children become the children of its parent. You have to process a query in such a way that maximizes the value of $c(v) - m \cdot k$ (where $c(v)$ is the resulting number of children of the vertex $v$ , and $m$ is the number of vertices you have deleted). Print the maximum possible value you can obtain.
The queries are independent: the changes you make to the tree while processing a query don't affect the tree in other queries.
输入格式
The first line contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of vertices in the tree.
Then $n-1$ lines follow, the $i$ -th of them contains two integers $x_i$ and $y_i$ ( $1 \le x_i, y_i \le n$ ; $x_i \ne y_i$ ) — the endpoints of the $i$ -th edge. These edges form a tree.
The next line contains one integer $q$ ( $1 \le q \le 2 \cdot 10^5$ ) — the number of queries.
Then $q$ lines follow, the $j$ -th of them contains two integers $v_j$ and $k_j$ ( $1 \le v_j \le n$ ; $0 \le k_j \le 2 \cdot 10^5$ ) — the parameters of the $j$ -th query.
Then $n-1$ lines follow, the $i$ -th of them contains two integers $x_i$ and $y_i$ ( $1 \le x_i, y_i \le n$ ; $x_i \ne y_i$ ) — the endpoints of the $i$ -th edge. These edges form a tree.
The next line contains one integer $q$ ( $1 \le q \le 2 \cdot 10^5$ ) — the number of queries.
Then $q$ lines follow, the $j$ -th of them contains two integers $v_j$ and $k_j$ ( $1 \le v_j \le n$ ; $0 \le k_j \le 2 \cdot 10^5$ ) — the parameters of the $j$ -th query.
输出格式
For each query, print one integer — the maximum value of $c(v) - m \cdot k$ you can achieve.
输入输出样例
输入 #1
8 6 7 3 2 8 3 5 7 7 4 7 1 7 3 6 1 0 1 2 1 3 7 1 5 0 7 200000
输出 #1
5 2 1 4 0 4
The tree in the first example is shown in the following picture:
Answers to the queries are obtained as follows:
1. $v=1,k=0$ : you can delete vertices $7$ and $3$ , so the vertex $1$ has $5$ children (vertices $2$ , $4$ , $5$ , $6$ , and $8$ ), and the score is $5 - 2 \cdot 0 = 5$ ;
2. $v=1,k=2$ : you can delete the vertex $7$ , so the vertex $1$ has $4$ children (vertices $3$ , $4$ , $5$ , and $6$ ), and the score is $4 - 1 \cdot 2 = 2$ .
3. $v=1,k=3$ : you shouldn't delete any vertices, so the vertex $1$ has only one child (vertex $7$ ), and the score is $1 - 0 \cdot 3 = 1$ ;
4. $v=7,k=1$ : you can delete the vertex $3$ , so the vertex $7$ has $5$ children (vertices $2$ , $4$ , $5$ , $6$ , and $8$ ), and the score is $5 - 1 \cdot 1 = 4$ ;
5. $v=5,k=0$ : no matter what you do, the vertex $5$ will have no children, so the score is $0$ ;
6. $v=7,k=200000$ : you shouldn't delete any vertices, so the vertex $7$ has $4$ children (vertices $3$ , $4$ , $5$ , and $6$ ), and the score is $4 - 0 \cdot 200000 = 4$ .
Answers to the queries are obtained as follows:
1. $v=1,k=0$ : you can delete vertices $7$ and $3$ , so the vertex $1$ has $5$ children (vertices $2$ , $4$ , $5$ , $6$ , and $8$ ), and the score is $5 - 2 \cdot 0 = 5$ ;
2. $v=1,k=2$ : you can delete the vertex $7$ , so the vertex $1$ has $4$ children (vertices $3$ , $4$ , $5$ , and $6$ ), and the score is $4 - 1 \cdot 2 = 2$ .
3. $v=1,k=3$ : you shouldn't delete any vertices, so the vertex $1$ has only one child (vertex $7$ ), and the score is $1 - 0 \cdot 3 = 1$ ;
4. $v=7,k=1$ : you can delete the vertex $3$ , so the vertex $7$ has $5$ children (vertices $2$ , $4$ , $5$ , $6$ , and $8$ ), and the score is $5 - 1 \cdot 1 = 4$ ;
5. $v=5,k=0$ : no matter what you do, the vertex $5$ will have no children, so the score is $0$ ;
6. $v=7,k=200000$ : you shouldn't delete any vertices, so the vertex $7$ has $4$ children (vertices $3$ , $4$ , $5$ , and $6$ ), and the score is $4 - 0 \cdot 200000 = 4$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted