河南省第十届acm情报传递
思想:建立领接表,将上司和下属中间建立一条有向边,权值初始化为1;
send 这样往上找上司的时候将路径上的值加上去就是所得的值,查找过的边就将值变为0,
Danger 删下属的时候,将值为0的恢复到1;
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int head[10000];
int n;
int len;
struct node{
int u;
int v;
int w;
int next;
}Route[10000];
vector<int >T[10000];
void add(int u,int v,int w){//邻接表
Route[len].u=u;
Route[len].v=v;
Route[len].w=w;
Route[len].next=head[u];
head[u]=len;
len++;
}
int Find(int end1){
int start=end1;
int sum=0;
int dx=head[end1];
while(start!=5065){//往下找上司,一直找的5065,将路径中的权值加上去
dx=head[start];
sum=sum+Route[dx].w;
Route[dx].w=0;//修改路径中的值。
start=Route[dx].v;
}
return sum;
}
int Del(int a){
queue<int >Q;
Q.push(a);
int q,w;
int sum=0;
while(!Q.empty()){
q=Q.front();
Q.pop();
for(int i=0;i<T[q].size();i++){
w=T[q][i];
int dx=head[w];
if(Route[dx].w==0)
{
sum++;
}
Route[dx].w=1;
Q.push(Route[dx].u);
}
}
return sum;
}
int main(){
scanf("%d",&n);
len=0;
memset(head,-1,sizeof(head));
//建立虚拟节点5065,这个点随意,只要测试数据里面没有这个点就行。
add(0,5065,1);
//记录下5065下属,删除节点的时候比较好找下属
T[5065].push_back(0);
int a;
for(int i=1;i<n;i++){
scanf("%d",&a);
add(i,a,1);//i是上司是a
T[a].push_back(i);//a的下属是i;
}
int m;
scanf("%d",&m);
char str[100];
for(int i=0;i<m;i++){
scanf("%s %d",str,&a);
if(str[0]=='S'){
printf("%d\n",Find(a));
}
else
{
int dx=head[a];
if(Route[dx].w==0){
printf("%d\n",Del(a)+1);
}
else
{
printf("%d\n",Del(a));
}
Route[dx].w=1;
}
}
return 0;
}
/*
10
0 1 2 1 3 0 0 3 2
10
S 0
S 3
D 2
S 7
S 5
S 9
D 9
S 4
S 1
S 9
*/