A16261 | Keen Tree Calculation
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
There is a tree of $N$ vertices and $N-1$ edges. The $i$ -th edge connects vertices $U_i$ and $V_i$ and has a length of $W_i$ .
Chaneka, the owner of the tree, asks you $Q$ times. For the $j$ -th question, the following is the question format:
- $X_j$ $K_j$ – If each edge that contains vertex $X_j$ has its length multiplied by $K_j$ , what is the diameter of the tree?
Notes:
- Each of Chaneka's question is independent, which means the changes in edge length do not influence the next questions.
- The diameter of a tree is the maximum possible distance between two different vertices in the tree.
Chaneka, the owner of the tree, asks you $Q$ times. For the $j$ -th question, the following is the question format:
- $X_j$ $K_j$ – If each edge that contains vertex $X_j$ has its length multiplied by $K_j$ , what is the diameter of the tree?
Notes:
- Each of Chaneka's question is independent, which means the changes in edge length do not influence the next questions.
- The diameter of a tree is the maximum possible distance between two different vertices in the tree.
输入格式
The first line contains a single integer $N$ ( $2\leq N\leq10^5$ ) — the number of vertices in the tree.
The $i$ -th of the next $N-1$ lines contains three integers $U_i$ , $V_i$ , and $W_i$ ( $1 \leq U_i,V_i \leq N$ ; $1\leq W_i\leq10^9$ ) — an edge that connects vertices $U_i$ and $V_i$ with a length of $W_i$ . The edges form a tree.
The $(N+1)$ -th line contains a single integer $Q$ ( $1\leq Q\leq10^5$ ) — the number of questions.
The $j$ -th of the next $Q$ lines contains two integers $X_j$ and $K_j$ as described ( $1 \leq X_j \leq N$ ; $1 \leq K_j \leq 10^9$ ).
The $i$ -th of the next $N-1$ lines contains three integers $U_i$ , $V_i$ , and $W_i$ ( $1 \leq U_i,V_i \leq N$ ; $1\leq W_i\leq10^9$ ) — an edge that connects vertices $U_i$ and $V_i$ with a length of $W_i$ . The edges form a tree.
The $(N+1)$ -th line contains a single integer $Q$ ( $1\leq Q\leq10^5$ ) — the number of questions.
The $j$ -th of the next $Q$ lines contains two integers $X_j$ and $K_j$ as described ( $1 \leq X_j \leq N$ ; $1 \leq K_j \leq 10^9$ ).
输出格式
Output $Q$ lines with an integer in each line. The integer in the $j$ -th line represents the diameter of the tree on the $j$ -th question.
输入输出样例
输入 #1
7 5 1 2 1 4 2 3 4 1 2 5 3 6 1 6 4 7 2 2 4 3 3 2
输出 #1
18 11
输入 #2
3 1 2 1000000000 2 3 1000000000 1 2 1000000000
输出 #2
2000000000000000000
In the first example, the following is the tree without any changes.
The following is the tree on the $1$ -st question.
The maximum distance is between vertices $6$ and $7$ , which is $6+6+6=18$ , so the diameter is $18$ .
The following is the tree on the $2$ -nd question.
The maximum distance is between vertices $2$ and $6$ , which is $3+2+6=11$ , so the diameter is $11$ .
The following is the tree on the $1$ -st question.
The maximum distance is between vertices $6$ and $7$ , which is $6+6+6=18$ , so the diameter is $18$ .
The following is the tree on the $2$ -nd question.
The maximum distance is between vertices $2$ and $6$ , which is $3+2+6=11$ , so the diameter is $11$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted