题目地址:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2170

题目大意

给你一颗N个节点的树,节点编号1到N。1总是节点的根。现在有两种操作:

  1. M v: 标记节点v
  2. Q v: 求出离v最近的标记的相邻节点。根节点一开始就标记好了。

现在给一系列操作,求出所有Q操作结果的和。

思路

第一次在AOJ上做题发现可以看数据,好评。。。

并查集系列。。建好树+标记节点即可,只是建树(合并)/搜索的时候不要压缩路径即可。。

这里有坑的地方就是,答案会超出32位数字范围。。还有就是如果$Q\ v$中,$v$被标记了那么离v最近的节点是$v$。

AC代码

/*************************************************************************
    > File Name: 2170.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-11-10 二 20:43:18 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
int par[100000+5];
bool marked[100000+5];
int N, Q;

void init() {
    for(int i=1; i<=N; ++i) par[i] = i;
}

void unite(int x, int y) { // 无需压缩。。
    if(x!=y) par[x] = y;
}


void solve() {
    memset(marked, 0, sizeof(marked));
    marked[1] = true; // 根节点是标记了的
    char op;
    int x=0;
    long long ans = 0;

    for(int i=0; i<Q; ++i) {
        cin >> op >> x;
        if(op == 'M')
            marked[x] = true;
        else {
            if(marked[x]) ans+=x; // 已经标记了那么还是它
            else {
                while(!marked[par[x]])
                    x = par[x];
                ans+=par[x];
            }
        }
    }

    cout << ans << endl;
}

int main()
{
#ifdef Oj
    // freopen("2170.in", "r", stdin);
#endif
    cin.sync_with_stdio(false);
    int father;
    while(cin >> N >> Q) {
        init();
        if(N == Q && Q==0) break;
        for(int i=2; i<=N; ++i) {
            cin >> father;
            unite(i, father); // 建树
        }
        solve();
    }
    return 0;
}