LYOJ 213 「雅礼集训 2017 Day8」爷

##题目描述

给你一个 $n$ 个点的有根树， $1$ 为根，带边权，有 $m$ 次操作。

* 求 $x$ 的子树中第 $k$ 小的深度的值，如果子树中没有$k$ 个点则输出 $-1$；
* 江 $x$ 与 $x$ 父亲的边权加上 $k$ 。

保证每次操作 2 的 $k$ 以及原树的边权小于等于一个数 $\text{len}$ 。

如果操作 2 中  $x$ 为 $1$，那么视为将 $x$ 的基础深度加上了 $k$。

##输入格式
第一行三个数 $n$、$m$ 、 $\text{len}$ 。之后 $n - 1$ 行每行两个数表示 $2 \sim n$ 每个点的父亲编号，以及他们到父亲的边权。
之后 $m$ 行每行三个数 $\text{opt}$、 $x$ 、 $k$， $\text{opt}$ 表示操作种类， $x$ 、$k$ 意义如题所述。

##输出格式

对于每个操作 1，输出一个数表示答案。

##样例

###样例输入
3 5 3
1 3
2 3
1 1 3
2 3 3
1 1 3
2 1 2
1 1 3
###样例输出
6
9
11
##数据范围与提示
对于 $10\%$ 的数据， $n, m \leq 1000$；
对于 $30\%$ 的数据， $n, m \leq 30000$；
对于 $100\%$ 的数据， $n, m \leq 100000, \text{len} \leq 10$。

##题解

标算复杂度$n\sqrt{n}logn$，一点都不优美。

考虑DFS序上动态分块。
从左到右，我们把深度差值不超过T,且大小不超过T,的分到一块，然后对于$1 \sim 2T$预处理出小于等于每个深度值的点有多少个。（显然有效范围不超过$2T$）
由于是一棵树，所以显然不会超过$\frac{2*N*10}{T}$块。

每次查询，就先二分深度，再在各个块中查询，如果是完整的一块，那么可以$O(1)$回答，不然暴力。

每次修改，对于一个整块就打标记，不然重构，重构时如果有相邻两个点的深度差超过$2T$，就分裂成两个块。

由于每次修改不超过10，所以所有操作完后，只有不超过$\frac{2*10*N}{T} + \frac{2*10*M}{T}$块

在T取到$O(\sqrt{n})$是得到最有理论复杂度。

实际上呢。。。你T取个3000左右就好了。数据水，块也不用动态分裂，直接开就好了。
![hehe](http://on9i1rseh.bkt.clouddn.com/hehe.jpg)

(被由乃大爷指出复杂度算错了。。。)

wuvin

导航

最近发表

友情链接