建设银行东航龙卡登录东航网站,网络营销工具及其特点,百度快照怎么看,wordpress短链接插件颜色平衡树问题描述格式输入格式输出样例输入样例输出评测用例规模与约定解析参考程序问题描述 格式输入
输入的第一行包含一个整数 n #xff0c;表示树的结点数。 接下来 n 行#xff0c;每行包含两个整数 Ci , Fi#xff0c;用一个空格分隔#xff0c;表示第 i 个结点 …
颜色平衡树问题描述格式输入格式输出样例输入样例输出评测用例规模与约定解析参考程序问题描述 格式输入
输入的第一行包含一个整数 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 ≤ 200Ci ≤ 200 对于 60% 的评测用例n ≤ 5000Ci ≤ 5000 对于所有评测用例1 ≤ n ≤ 2000001 ≤ Ci ≤ 2000000 ≤ Fi i 。 解析
十四届蓝桥 参考程序
#includebits/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_mapint, 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;
}
以个人刷题整理为目的如若侵权请联系删除~
