Responsive image

问题 1778 --情报传递

1778: 情报传递

时间限制: 2 Sec  内存限制: 128 MB
提交: 50  解决: 14
[提交][状态][讨论版][命题人:]

题目描述

抗日战争时期,在国共合作的大背景下,中共不断发展壮大,其情报工作也开始由获取警报性、保卫性信息,向获取军政战略性情报转变。各系统情报组织遵循"荫蔽精干,长期埋伏,积蓄力量,以待时机"的隐蔽战线工作方针,开展了卓有成效的情报工作。

***特科组是中共情报工作的一个杰出范例,它以点为主、系统延伸、分散辐射的力量格局,异地领导、分头派遣、单线联系的组织形式。以打入、拉出、统战联络、内线为主的工作方式,形成了一个传递信息隐蔽、效用及时、形式多样的情报网络。

***特科组的情报人员共有N人,其代号分别为0,1……,N-1 0号是最高领导人,特工之间有一套严格的单线联络程序,即,每个特工人员只有一个上线,他获得的情报需层层上传递到0号手里,由0号发报出去。

特工i在传递情报时,若通往到0号的通道尚未建立,则需要建立一级级单线通道;若他的上线已建立好通道,只需建立两人通道,信息发送给上线;依次类推。若特工i已建立好到0号的通道,则直接发出情报。日伪统治中心南京,既是情报来源丰富的地方,又是特工人员活动最危险的地方。因此,一旦某个特工处于不安全状态,他必须马上撤离,同时他的所有下线(处在通道上的一级级下线)也一同撤离。

已知***特科组的组织结构,你的任务是计算,当某特工i需要发送情报时,最少需要建立几个情报人员的通道;当某特工i处于不安全状态时,最少需要撤离多少人员。

输入描述

第一行一个整数:  N           ( 1≤N ≤5060

接下来一行有N-1 个整数,  A1 A2 ……An-1  ,其中Ai是编号i的上线。

下一行一个整数:  M         表示有M个状态,( 1≤M ≤5060 )

接下来有M行 :有两种形式:  Send i    特工i处于要发送情报状态;

                             Danger i  特工i处于不安全状态

输出描述

输出占M行 ,对于Send i,输出最少需要建立通道的情报人员数,若特工i处于通道线上,输出0;对于Danger i,输出最少需要撤离多少人员,若特工i不处于通道线上,则输出0.

样例输入

10
0 1 2 1 3 0 0 3 2
10
Send 0
Send 3
Danger 2
Send 7
Send 5
Send 9
Danger 9
Send 4
Send 1
Send 9

样例输出

1
3
2
1
3
1
1
1
0
1

来源

[提交][状态]
ACM算法攻关部