提示: 欢迎访问OurACM平台。
Problem 2119 祖先问题

Accept: 19    Submit: 107
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

有n个结点构成了多棵树,给出每个结点的父节点,若为-1则表示该结点无父节点。每个结点的父节点编号必须比该结点的编号小。给m个操作,有两种操作:1.重新设置某结点的父节点;2.求某结点的祖先个数。一个结点的祖先为其父节点及其父节点的祖先。

Input

有多组数据输入。每组数据的第一行为两个整数n,m。(1<=n,m<=200000)。第二行输入n个数,从1到n分别表示编号为1到n的结点的父节点,若为-1则表示该结点无父节点。接下来输入m行,表示m个操作,每行输入有两种:三个数t,a,b(t=0,1<= a <=n,b为-1或小于a的正整数),将结点a的父节点设置为b,若b为-1则表示将a设为无父节点;或者两个数t,a(t=1,1<=a<=n),表示询问结点a的祖先个数。数据保证每个结点的父节点编号比该结点小。所有输入都为整数。

Output

对于每个询问输出一行一个整数,表示该结点的祖先数。

Sample Input

4 3 -1 1 2 3 1 4 0 4 1 1 4

Sample Output

3 1

Source

FOJ有奖月赛-2013年4月(校赛热身赛)

Submit  Back  Status  Discuss