Rt.

[USACO08DEC]Trick or Treat on the Farm G

题面翻译

题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在 $N(1\le N\le 100,000)$ 个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ 通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ 在第 $i$ 号隔间上张贴了一个“下一个隔间：$next_i(1\le next_i\le N)$”的标语，告诉奶牛要去的下一个隔间。这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ 命令奶牛 $i$ 应该从 $i$ 号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

输入格式

第一行一个整数 $n$，表示牛棚隔间的数量。

第 $2$ 至 $n+1$ 行 每行包含一个整数 $next_i$，表示 $i$ 号隔间的下一个隔间。

输出格式

输出共 $n$ 行，第 $i$ 行包含一个整数，表示第 $i$ 只奶牛要前往的隔间数。

样例解释

有 $4$ 个隔间。

• 隔间 $1$ 要求牛到隔间 $1$，

• 隔间 $2$ 要求牛到隔间 $3$，

• 隔间 $3$ 要求牛到隔间 $2$，

• 隔间 $4$ 要求牛到隔间 $3$。

牛 $1$：从 $1\rightarrow 1$，总共访问 $1$ 个隔间；

牛 $2$：$2\rightarrow 3\rightarrow 2$，总共访问 $2$ 个隔间；

牛 $3$：$3\rightarrow 2\rightarrow 3$，总共访问 $2$ 个隔间；

牛 $4$：$4\rightarrow 3\rightarrow 2\rightarrow 3$，总共访问3个隔间。

翻译提供者：busy_programmer

# [USACO08DEC]Trick or Treat on the Farm G

## 题面翻译

#### 题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在 $N(1\le N\le 100,000)$ 个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ 通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ 在第 $i$ 号隔间上张贴了一个“下一个隔间：$next_i(1\le next_i\le N)$”的标语，告诉奶牛要去的下一个隔间。这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ 命令奶牛 $i$ 应该从 $i$ 号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

#### 输入格式

第一行一个整数 $n$，表示牛棚隔间的数量。

第 $2$ 至 $n+1$ 行 每行包含一个整数 $next_i$，表示 $i$ 号隔间的下一个隔间。

#### 输出格式

输出共 $n$ 行，第 $i$ 行包含一个整数，表示第 $i$ 只奶牛要前往的隔间数。

#### 样例解释

有 $4$ 个隔间。

- 隔间 $1$ 要求牛到隔间 $1$，

- 隔间 $2$ 要求牛到隔间 $3$，

- 隔间 $3$ 要求牛到隔间 $2$，

- 隔间 $4$ 要求牛到隔间 $3$。

牛 $1$：从 $1\rightarrow 1$，总共访问 $1$ 个隔间；

牛 $2$：$2\rightarrow 3\rightarrow 2$，总共访问 $2$ 个隔间；

牛 $3$：$3\rightarrow 2\rightarrow 3$，总共访问 $2$ 个隔间；

牛 $4$：$4\rightarrow 3\rightarrow 2\rightarrow 3$，总共访问3个隔间。

翻译提供者：[busy_programmer](https://www.luogu.com.cn/user/649315)