第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 E 题

问题描述

---

格式输入

输入的第一行包含一个整数 n ，表示树的结点数。
接下来 n 行，每行包含两个整数 Ci
, Fi，用一个空格分隔，表示第 i 个结点
的颜色和父亲结点编号。
特别地，输入数据保证 F1 为 0 ，也即 1 号点没有父亲结点。保证输入数
据是一棵树。

---

格式输出

输出一行包含一个整数表示答案。

---

样例输入

6
2 0
2 1
1 2
3 3
3 4
1 4

---

样例输出

4 编号为 1, 3, 5, 6 的 4 个结点对应的子树为颜色平衡树。

---

评测用例规模与约定

对于 30% 的评测用例，n ≤ 200，Ci ≤ 200 ；
对于 60% 的评测用例，n ≤ 5000，Ci ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ Ci ≤ 200000，0 ≤ Fi < i 。

---

解析

十四届蓝桥

---

参考程序

#include<bits/stdc++.h>
using namespace std;
const int N = 200000 + 7;
int col[N], f, n, ans;
struct node {int to, next;
}edge[N];
int head[N], cnt, num[N];
inline void add(int x, int to) {edge[++cnt].to = to;edge[cnt].next = head[x];head[x] = cnt;
}
int dfn, in[N], out[N], belong[N], newcol[N];
unordered_map<int, int> mp;
inline void dfs(int x) {in[x] = ++dfn;for (int i = head[x]; i; i = edge[i].next) {int y = edge[i].to;dfs(y);}out[x] = dfn;
}
struct mo {int l, r;
}q[N << 1];
inline bool cmp(const mo& a, const mo& b) {return belong[a.l] == belong[b.l] ? a.r < b.r : a.l < b.l;
}
inline void del(int x) {int c = newcol[x];mp[num[c]]--;if (mp[num[c]] == 0) {mp.erase(num[c]);}num[c]--;if (num[c]) mp[num[c]]++;
}
inline void add(int x) {int c = newcol[x];if (num[c]) mp[num[c]]--;if (mp[num[c]] == 0) {mp.erase(num[c]);}num[c]++;mp[num[c]]++;
}
inline void Case_Test() {cin >> n;for (int i = 1; i <= n; i++) {cin >> col[i] >> f;if (f) add(f, i);}dfs(1);for (int i = 1; i <= n; i++) {// cout << i << " : [" << in[i] << "," << out[i] << "]" << endl;q[i].l = in[i], q[i].r = out[i];newcol[in[i]] = col[i]; newcol[out[i]] = col[i];// dfn改变原来位置，需要用newcol}int sq = sqrt(dfn);// 根号for (int i = 1; i <= dfn; i++) {belong[i] = (i - 1) / sq + 1;// 预处理}sort(q + 1, q + 1 + n, cmp);// 查询区间排序int l = 1, r = 0;// 莫队初始化for (int i = 1; i <= n; i++) {while (l < q[i].l) del(l++);while (l > q[i].l) add(--l);while (r < q[i].r) add(++r);while (r > q[i].r) del(r--);// 莫队四种转移if (mp.size() == 1) ans++;}cout << ans;
}
int main()
{Case_Test();return 0;
}

以个人刷题整理为目的，如若侵权，请联系删除~