#PU817. USACO 2018 February Contest, Platinum — Problem 2. New Barns

    ID: 1384 传统题 文件IO:newbarn 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb18来源:usaco.orgscoring:equal_test_cases并查集

USACO 2018 February Contest, Platinum — Problem 2. New Barns

USACO 2018 February Contest, Platinum — Problem 2. New Barns

题目描述

Farmer John notices that his cows tend to get into arguments if they are packed too closely together, so he wants to open a series of new barns to help spread them out. Whenever FJ constructs a new barn, he connects it with at most one bidirectional pathway to an existing barn. In order to make sure his cows are spread sufficiently far apart, he sometimes wants to determine the distance from a certain barn to the farthest possible barn reachable from it (the distance between two barns is the number of paths one must traverse to go from one barn to the other). FJ will give a total of QQ (1≤Q≤1051 \leq Q \leq 10^5) queries, each either of the form "build" or "distance". For a build query, FJ builds a barn and links it with at most one previously built barn. For a distance query, FJ asks you the distance from a certain barn to the farthest barn reachable from it via a series of pathways. It is guaranteed that the queried barn has already been built. Please help FJ answer all of these queries.

输入格式

The first line contains the integer QQ. Each of the next QQ lines contains a query. Each query is of the form "B p" or "Q k", respectively telling you to build a barn and connect it with barn pp, or give the farthest distance, as defined, from barn kk. If p=−1p = -1, then the new barn will be connected to no other barn. Otherwise, pp is the index of a barn that has already been built. The barn indices start from 11, so the first barn built is barn 11, the second is barn 22, and so on.

输出格式

Please write one line of output for each distance query. Note that a barn which is connected to no other barns has farthest distance 00.

数据范围

(见题面原文)

样例

样例 1

7

B -1

Q 1

B 1

B 2

Q 3

B 2

Q 2
0

2

1
The example input corresponds to this network of barns:
(1) 
    \   
     (2)---(4)
    /
  (3)
In query 1, we build barn number 1. In query 2, we ask for the distance of 1 to
the farthest connected barn. Since barn 1 is connected to no other barns, the
answer is 0. In query 3, we build barn number 2 and connect it to barn 1. In
query 4, we build barn number 3 and connect it to barn 2. In query 5, we ask for
the distance of 3 to the farthest connected barn. In this case, the farthest is
barn 1, which is 2 units away. In query 6, we build barn number 4 and connect it
to barn 2. In query 7, we ask for the distance of 2 to the farthest connected
barn. All three barns 1, 3, 4 are the same distance away, which is 1, so this is
our answer.
Problem credits: Anson Hu