| 题目名称 | 2910. [USACO Feb18] 新牛棚 |
|---|---|
| 输入输出 | newbarns.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 WHZ0325
于2018-03-02加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：7， 通过率：28.57% | ||||
 Satoshi |
100 | 2.504 s | 8.57 MiB | C++ |
 hyghb |
100 | 3.697 s | 12.14 MiB | C++ |
|
hyghb |
80 | 3.294 s | 10.93 MiB | C++ |
|
hyghb |
80 | 3.672 s | 10.93 MiB | C++ |
 exkd |
0 | 0.084 s | 56.39 MiB | C++ |
 __stdcall |
0 | 0.109 s | 4.49 MiB | C++ |
|
hyghb |
0 | 1.856 s | 10.24 MiB | C++ |
| 关于 新牛棚 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
动态维护树的直径即可，(注意这不是一个树而是森林), 用每棵树的第一个插入点代表这棵树，预处理每棵树的倍增$LCA$数组，则对树中任意两点的距离的询问可以在$O(logn)$的时间内求得，然后把整个森林重建一遍-----设新加入的点为$k$ 当前树的直径端点为$i$和$j$(初始的$i,j$为根结点)，如果$dis(i,k)>dis(i,j)$那么把直径的端点$j$换成$k$,如果$dis(j,k)>dis(i,j)$那么把直径的端点$i$换成$k$，最后得到的就是树的真正直径.
| ||||
【题目描述】
Farmer John注意到他的奶牛们如果被关得太紧就容易吵架，所以他想开放一些新的牛棚来分散她们。
每当FJ建造一个新牛棚的时候，他会将这个牛棚用至多一条双向道路与一个现有的牛棚连接起来。为了确保他的奶牛们足够分散，他有时想要确定从某个特定的牛棚出发，到它能够到达的最远的牛棚的距离（两个牛棚之间的距离等于从一个牛棚出发到另一个之间必须经过的道路条数）。
FJ总共会给出$Q$（$1≤Q≤10^5$）次请求，每个请求都是“建造”和“距离”之一。对于一个建造请求，FJ建造一个牛棚，并将其与至多一个现有的牛棚连接起来。对于一个距离请求，FJ向你询问从某个特定的牛棚通过一些道路到离它最远的牛棚的距离。保证询问的牛棚已经被建造。请帮助FJ响应所有的请求。
【输入格式】
第一行包含一个整数$Q$。以下$Q$行，每行包含一个请求。每个请求的格式都是“B p”或是“Q k”，分别告诉你建造一个牛棚并与牛棚$p$连接，或是根据定义求从牛棚$k$出发最远的距离。如果$p=−1$，则新的牛棚不会与其他牛棚连接。否则，$p$是一个已经建造的牛棚的编号。牛棚编号从$1$开始，所以第一个被建造的谷仓是$1$号谷仓，第二个是$2$号谷仓，以此类推。
【输出格式】
对于每个距离请求输出一行。注意一个没有连接到其他牛棚的牛棚的最远距离为$0$。
【样例输入】
7 B -1 Q 1 B 1 B 2 Q 3 B 2 Q 2
【样例输出】
0 2 1
【提示】
输入样例对应下面的牛棚网：
(1)
\
(2)---(4)
/
(3)
对于请求1，我们建造牛棚1。对于请求2，我们询问从1出发到最远连接的牛棚的距离。由于牛棚1没有与其他牛棚连接，所以回答是0。对于请求3，我们建造牛棚2并将其与牛棚1连接。对于请求4，我们建造牛棚3并将其与牛棚2连接。对于请求5，我们询问从3出发到最远连接的牛棚的距离。在这时，最远的是牛棚1，距离为2单位。对于请求6，我们建造牛棚4并将其与牛棚2连接。对于请求7，我们询问从2出发到最远连接的牛棚的距离。所有其他三个牛棚1，3，4都与2相距相同的距离1，所以这就是我们的回答。
【来源】
USACO Feb18 Platinum New Barns
供题：Anson Hu