题意:出一颗树,有两种操作:
1. mark u 标记结点u
2.query u 询问离u最近的且被标记的祖先结点是哪个
让你输出所有询问的和。
思路:数据量太小,直接暴力dfs就可以了
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#define MAXSIZE 100005
#define LL long long
using namespace std; int vis[MAXSIZE],pre[MAXSIZE]; LL dfs(int p)
{
if(vis[p])
return p;
return dfs(pre[p]);
} int main()
{
int n,m,num;
LL sum;
char op[];
while(scanf("%d%d",&n,&m),n+m)
{
sum = ;
memset(vis,,sizeof(vis));
vis[] = ;
for(int i=;i<=n;i++)
{
scanf("%d",&num);
pre[i] = num;
} while(m--)
{
scanf("%s%d",op,&num);
if(op[] == 'Q')
{
sum += dfs(num);
} else
{
vis[num] = ;
}
} printf("%lld\n",sum);
}
return ;
}