Skip to content

11045: 【原1045】二哥的家族

题目

题目描述

author: oldherl 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1045

Description

二哥的家族(简称二家)有详细记录家谱的传统，当然和其他的家谱一样里面是只记录雄性成员的。

维护家谱是一件很麻烦的事。二家不时有人出生或死去，都需要及时反映在家谱上。

当一个二家的(雄性的)人出生时，就要写在他的父亲的下面。当一个二家的(雄性的)人死去时，他的儿子们(如果有的话)就会带着各自的子孙们(如果有的话)离开他们的祖父/叔叔/大爷们，各自成为一个新的家。

没出生的人和死人是不能生育后代的(废话)，而且不允许孩子出生时父亲已经死去这种情况(别问我为啥，这也是二家的规定)。

春节时每家都要派出一个人参加“二家代表大会”(简称二会)，所以就需要知道二家此时有几个家。

初始时二家只有一个人(也就是二哥)。

Input Format

二哥的编号为1

第 1 行：一个整数 N 表示下面的行数。

第 2..N+1 行：每行是以下三种操作之一：

B x y 其中x和y是两个整数，表示编号为x的人(保证存在)有了一个编号为y的孩子

D x 其中x是一个整数，表示编号为x的人(保证存在)死去了

Output Format

对于每一个D操作，输出一个整数表示这个人死了以后二家有几个家。

Hint

对100%的数据，3 <= N <= 200000。

题目中出现的所有数均为不超过 200000 的正整数。

同一时间活着的人的编号不会重复。

Sample Input

7
B 1 2
B 1 3
D 1
B 2 4
B 4 5
B 2 6
D 4

Sample Output

2
3

FineArtz's solution 

/* 二哥的家族 */
#include <iostream>
using namespace std;

bool b[200005] = {0};
int father[200005] = {0}, son[200005] = {0};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, cnt = 1;
    cin >> n;
    b[1] = true;
    while (n--){
        char ch;
        cin >> ch;
        if (ch == 'B'){
            int x, y;
            cin >> x >> y;
            father[y] = x;
            ++son[x];
            b[y] = true;
        }
        else if (ch == 'D'){
            int x;
            cin >> x;
            if (b[father[x]]){
                cnt += son[x];
                --son[father[x]];
            }
            else
                cnt += son[x] - 1;
            b[x] = false;
            son[x] = 0;
            cout << cnt << '\n';
        }
    }
    return 0;
}

ligongzzz's solution 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

class person {
public:
    int parent = 0, childnum = 0;
    bool status = true;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    unordered_map<int, int> person_map;
    vector<person> vdata;
    int total_cnt = 1, ans = 1;

    //Init
    person fiperson;
    fiperson.status = false;
    vdata.emplace_back(fiperson);
    fiperson.status = true;
    vdata.emplace_back(fiperson);
    person_map.insert(make_pair(1, 1));

    for (; n; --n) {
        string ch;
        cin >> ch;

        if (ch == "B") {
            int x, y;
            cin >> x >> y;
            person tmp;
            tmp.parent = person_map[x];
            vdata[person_map[x]].childnum++;
            vdata.emplace_back(tmp);
            person_map.insert(make_pair(y, ++total_cnt));
        }
        else if (ch == "D") {
            int x;
            cin >> x;
            vdata[person_map[x]].status = false;
            if (!vdata[person_map[x]].parent || !vdata[vdata[person_map[x]].parent].status) {
                ans += vdata[person_map[x]].childnum - 1;
            }
            else {
                --vdata[vdata[person_map[x]].parent].childnum;
                ans += vdata[person_map[x]].childnum;
            }
            person_map.erase(x);
            cout << ans << "\n";
        }
    }

    return 0;
}

WashSwang's solution 

#include <iostream>
#include <cstdio>
using namespace std;
int total,fa[300000],son[300000],n,x,y;
char c;
bool die[300000];
int main() {
    fa[1]=0;
    die[0]=true;
    total=1;
    scanf("%d",&n);
    for (int i=0;i<n;++i){
        c=0;
       while (c!='B'&&c!='D') c=getchar();
       if (c=='B'){
           scanf("%d%d",&x,&y);
           fa[y]=x;
           son[x]++;
       }
       if (c=='D'){
           scanf("%d",&x);
           die[x]=true;
           if (die[fa[x]])
               total+=son[x]-1;
           else {
               son[fa[x]]-=1;
               total += son[x];
           }
           son[x]=0;
           printf("%d\n",total);
       }
    }
    return 0;
}

yyong119's solution 

#include <iostream>
#include <cstring>
#include <cstdio>

int father[200001], son[200001];
bool alive[200001];
char Data;
int n, i, num, a, b;

using namespace std;

void Solvedead(int Dindex) {

    if (alive[father[Dindex]] == false) {
        num += son[Dindex] - 1;
    } else {
        son[father[Dindex]] -= 1;
        num += son[Dindex];
    }
    father[Dindex] = Dindex;
    alive[Dindex] = false;
    printf("%d\n", num);
}

int main() {
    scanf("%d", &n);
    num = 1;
    father[1] = 1;
    memset(alive, true, sizeof(alive));
    for (i = 1; i <= n; i++) {
        scanf("%s", &Data);
        if (Data == 'B') {
            scanf("%d%d", &a, &b);
            father[b] = a;
            son[a] += 1;
        }
        else {
            scanf("%d", &a);
            Solvedead(a);
        }
    }
    return 0;
}