模拟一下 就可 ，如果用邻接表模拟 只能是单向，双向 太麻烦，还有就是利用vector来存储，因为每个人都只有一个上级，因此定义结构体，每个结构体里存储所有儿子与一个父节点，还有一个flag标记 边。建通道时 不断取父节点，删除时用bfs删；
#include<iostream> #include <string.h> #include <vector> #include <queue> using namespace std; struct vect{ vector<int>ve; int father; int flag; }; vect vec[5080]; int main() { int n,va,t,sum,a; char ch[10]; cin>>n; memset(vec,0,sizeof(vec)); for (int i=1;i<=n-1;i++) { cin>>a; vec[a].ve.push_back(i); vec[i].father=a; } vec[0].father=-1;//因为 0的时候答案是一，因此0上面也有个通道，假设0的父亲为-1； cin>>t; while(t--) { scanf("%s%d",ch,&va); sum=0; if (ch[0]=='S') { while(1) { if (va==-1||vec[va].flag==1) break; vec[va].flag=1; va=vec[va].father; sum++; } cout<<sum<<endl; } else if (ch[0]=='D') { sum=1; int dat=vec[va].flag; queue<int>q; while (!q.empty()) q.pop(); q.push(va); while (!q.empty()) { int s=q.front(); q.pop(); if (vec[s].flag) { if (s!=va) sum++; vec[s].flag=0; } int si=vec[s].ve.size(); for (int i=0;i<si;i++) { int xx=vec[s].ve[i]; if (vec[xx].flag==1) q.push(xx); } } if (sum==1&&dat==0)//注意如果va不在通道上 输出0， 而不会输出他自己 cout<<"0"<<endl; else cout<<sum<<endl; } } return 0; }