2020-2021:teams:hotpot:200808-200814
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:200808-200814 [2020/08/14 14:49] misakatao 更新 |
2020-2021:teams:hotpot:200808-200814 [2020/08/14 15:01] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 88: | 行 88: | ||
| 陶吟翔： | 陶吟翔： | ||
| - | 题目大意： | + | 题目大意：给出一棵$n$个点的树，边有边权，每次可以把一条路径上的边权减一，问最少多少次可以把所有边权减成零，另外有$q$个询问，每次修改一条边的边权，对每个询问也要回答 |
| - | 数据范围： | + | 数据范围：$1 \le n,q \le 10^5$，$1 \le w_i \le 10^9$ |
| - | 解题思路： | + | 解题思路：对于每一个点单独考虑连向子树的边，我们假设$a$是连向子树的边中最大的，$t$是这个点连向父亲的边，显然我们可以把$t$个删除和连向父亲的边一起做，剩下的就必须在子树内解决，所以我们根据经典的电池问题，检查$2 \times a$和$t + sum$的大小然后计算这一个点对答案的贡献。对于修改，显然只会影响两个点的答案，我们再单独处理这两个点即可 |
| - | 推荐理由： | + | 推荐理由：从题目本身到答案本质的计算需要一定的模型转化能力，并且处理答案时的细节处理也比较复杂，全面地考察了做题者的能力 |
| 郭衍培： | 郭衍培： | ||
2020-2021/teams/hotpot/200808-200814.1597387767.txt.gz · 最后更改: 2020/08/14 14:49 由 misakatao
