BZOJ_3011_[Usaco2012 Dec]Running Away From the Barn _可并堆

Description

给出以1号点为根的一棵有根树,问每个点的子树中与它距离小于l的点有多少个。

Sample Input

4 5
1 4
2 3
1 5

Sample Output

3
2
1
1


做法不唯一,这里用来练习可并堆。

先求出每个点$i$ 到根路径上的长度$dis[i]$ ,对每个点建一个可并堆(大根)。

然后从下往上合并,如果当前$dis[堆顶]-dis[x]>L$ 就弹出,记录每个节点最后剩下的点数即可。

代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 200050
typedef long long ll;
ll val[N<<1],L,v[N];
int head[N],to[N<<1],nxt[N<<1],cnt,n,root[N],ls[N],rs[N],dis[N],siz[N];
inline void add(int u,int v,ll w) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
int merge(int x,int y) {
if(!x) return y;
if(!y) return x;
if(v[x]<v[y]) swap(x,y);
rs[x]=merge(rs[x],y);
if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
dis[x]=dis[rs[x]]+1;
return x;
}
void dfs(int x,int y) {
int i;
siz[x]=1; root[x]=x;
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
v[to[i]]=v[x]+val[i];
dfs(to[i],x);
siz[x]+=siz[to[i]];
root[x]=merge(root[x],root[to[i]]);
}
}
while(v[root[x]]-v[x]>L) {
siz[x]--; root[x]=merge(ls[root[x]],rs[root[x]]);
}
}
int main() {
dis[0]=-1;
scanf("%d%lld",&n,&L);
int i,x;
ll y;
for(i=2;i<=n;i++) {
scanf("%d%lld",&x,&y);
add(i,x,y); add(x,i,y);
}
dfs(1,0);
for(i=1;i<=n;i++) {
printf("%d\n",siz[i]);
}
}

最新文章

  1. jQuery插件(cookie存值)
  2. DB2中错误信息说明
  3. Android MP3录音实现
  4. POJ C++程序设计 编程作业—类和对象 编程题 #2
  5. sharepoint SPFolder的使用
  6. 解决安装Visual Studio 2012后SQL Server 2008 远程过程调用失败的问题
  7. Android SDK Manager安装报错
  8. Understanding Neural Networks Through Deep Visualization
  9. 用smarty模板做数据实现修改、分页等功能
  10. Taffy自动化测试框架简介
  11. LeetCode之Easy篇 ——(1)Two Sum
  12. 安装PackageControl
  13. February 12th, 2018 Week 7th Monday
  14. 各类nosql db的功能与性能对比
  15. 《shiro框架》
  16. Go 语言简介(上)— 语法
  17. koan重装system
  18. Net Quartz使用
  19. POJ 2689 筛法求素数
  20. 30 个免费的 Sketch 必备插件

热门文章

  1. Scala访问修饰符(四)
  2. PHP环境的搭建(Apache)
  3. UML类图简单介绍
  4. fdisk分区硬盘并shell脚本自动化
  5. AP_AP系列 - 付款管理分析(案例)
  6. IO和NIO的区别
  7. iOS学习网站及大牛网址(实时更新)
  8. 用sublime编译C++的方法
  9. Windows内存原理与内存管理
  10. SpringMVC Controller详解
  11. Android文字的阴影效果
  12. UVa 11129 - An antiarithmetic permutation
  13. Runtime系列(二)--Runtime的使用场景
  14. POJ2385——Apple Catching
  15. 【bzoj 4833】[Lydsy1704月赛]最小公倍佩尔数
  16. android 异常信息The specified child already has a parent. You must call removeView() on the child&#39;s parent first. 的处理方法
  17. Nginx Java 日志切割脚本
  18. django组件:中间件
  19. .net core和.net 4.7区别和联系笔记
  20. visual studio 修改注释快捷键,和断点