Aizu 2170 Marked Ancestor

题意:出一颗树,有两种操作:
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 ;
}
上一篇:Android 常见对话框的简单使用(提示信息对话框、单选多选对话框、自定义对话框)


下一篇:JAVA回调机制和观察者模式实例分享