2020-2021:teams:farmer_john:2016_icpc_沈阳站
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2016_icpc_沈阳站 [2020/10/13 22:24] jjleo [题意] |
2020-2021:teams:farmer_john:2016_icpc_沈阳站 [2020/10/17 16:09] (当前版本) jjleo [H.] |
||
|---|---|---|---|
| 行 41: | 行 41: | ||
| [[https://www.cnblogs.com/dilthey/p/9973558.html|参考链接]] | [[https://www.cnblogs.com/dilthey/p/9973558.html|参考链接]] | ||
| =====H.===== | =====H.===== | ||
| - | **upsolved by ** | + | **upsolved by JJLeo** |
| ====题意==== | ====题意==== | ||
| 行 57: | 行 57: | ||
| 给定一棵节点数为 $n$ 基环树，$q$ 次操作，分为两种：将所有距离点 $x$ 不超过 $d$ 的点加上一个值，或询问所有距离点 $x$ 不超过 $d$ 的点的权值之和。$(n, q \le 10^5, d \le 2)$ | 给定一棵节点数为 $n$ 基环树，$q$ 次操作，分为两种：将所有距离点 $x$ 不超过 $d$ 的点加上一个值，或询问所有距离点 $x$ 不超过 $d$ 的点的权值之和。$(n, q \le 10^5, d \le 2)$ | ||
| ====题解==== | ====题解==== | ||
| + | 如果是一棵树，那么对于一个节点，需要考虑的就只有它的父亲，它的爷爷，它的兄弟，它的儿子和它的孙子。考虑对树进行bfs，那么上述的bfs序各自构成一个连续的区间，使用线段树维护即可。 | ||
| + | |||
| + | 本题是基环树，因此需要讨论一波，对于环上的点，考虑对于环上临近的1个或2个点即可，注意去重，以及当 $d=2$ 时且选中点为环上点时，要考虑环上临近点的所有儿子。 | ||
| =====记录===== | =====记录===== | ||
| =====总结===== | =====总结===== | ||
| + | * ZYF：J题分类讨论完全正确，但是算法完全想错了，$O(n)$ 维护不太可能，太想当然了。 | ||
2020-2021/teams/farmer_john/2016_icpc_沈阳站.1602599090.txt.gz · 最后更改: 2020/10/13 22:24 由 jjleo
