当前位置: 首页 > news >正文

网站建设风险怎样规避刷外链工具

网站建设风险怎样规避,刷外链工具,av网站正在建设中,北京专门做网站的公司颜色平衡树问题描述格式输入格式输出样例输入样例输出评测用例规模与约定解析参考程序问题描述 格式输入 输入的第一行包含一个整数 n ,表示树的结点数。 接下来 n 行,每行包含两个整数 Ci , Fi,用一个空格分隔,表示第 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 ≤ 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;
}

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

http://www.15wanjia.com/news/18482.html

相关文章:

  • 安装wordpress 空白页win7系统优化工具
  • 本溪网站制作云资源软文发布平台
  • 国外赚钱平台优化设计七年级上册数学答案
  • 网站维护运营优化公司建网站费用
  • 国家企业信用公示信息系统(安徽)郑州网站seo服务
  • githuub怎么做网站天津做网站的公司
  • 网站建设的合同书网页设计效果图及代码
  • 西宁做网站公司排名怎么做个人网页
  • 做项目的编程网站百度推广关键词
  • wordpress网站底部导航代码江苏seo推广
  • 长春网站推广优化公司百度站长工具排名
  • 用vs2013做网站案例网站优化排名服务
  • 深圳品牌网站建设个人网站模板免费下载
  • 中为网站建设怎么提交百度收录
  • 宁波网络公司报价外包seo公司
  • 中山网站建设文化价格网络推广比较经典和常用的方法有
  • 深圳网站建设公司模板学习软件的网站
  • 想自己做个网站怎么做百度推广客户端电脑版
  • 网站开发论文研究方法东莞互联网公司排名
  • 广西自治区集约化网站建设要求国际军事最新消息今天
  • 网站建设沧州怎么在网上做广告宣传
  • 营销型企业网站分析与诊断的步骤网站建设品牌公司
  • 百度推广区域代理硬件优化大师
  • 无人机公司网站建设seo整站优化更能准确获得客户
  • 深圳网站建设企业名录免费网站免费
  • 上海网站 备案谷歌seo网站运营
  • 网站上的vr全景是怎么做的兰州网络推广公司哪家好
  • 吉林省人民政府办公厅官网网站seo站外优化
  • 网站定制电话江苏seo团队
  • 不参与网站建设的弊端企业qq官网