題意：出一顆樹(shù)，有兩種操作：
1. mark? u? 標(biāo)記結(jié)點(diǎn)u
2.query? u? 詢問(wèn)離u最近的且被標(biāo)記的祖先結(jié)點(diǎn)是哪個(gè)
讓你輸出所有詢問(wèn)的和。

?

思路：數(shù)據(jù)量太小，直接暴力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[5];while(scanf("%d%d",&n,&m),n+m){sum = 0;memset(vis,0,sizeof(vis));vis[1] = 1;for(int i=2;i<=n;i++){scanf("%d",&num);pre[i] = num;}while(m--){scanf("%s%d",op,&num);if(op[0] == 'Q'){sum += dfs(num);}else{vis[num] = 1;}}printf("%lld\n",sum);}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/alan-W/p/7288460.html

總結(jié)

以上是生活随笔為你收集整理的Aizu 2170 Marked Ancestor的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。