11045: 【原1045】二哥的家族

题目描述

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

Input Format

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

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

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;

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);