题面
题目描述
给出以1号点为根的一棵有根树，问每个点的子树中与它距离小于等于l的点有多少个。
输入格式：
Line 1: 2 integers, N and L (1 <= N <= 200,000, 1 <= L <= 10^18)
Lines 2..N: The ith line contains two integers p_i and l_i. p_i (1 <= p_i < i) is the first pasture on the shortest path between pasture i and the barn, and l_i (1 <= l_i <= 10^12) is the length of that path.
输出格式：
Lines 1..N: One number per line, the number on line i is the number pastures that can be reached from pasture i by taking roads that lead strictly farther away from the barn (pasture 1) whose total length does not exceed L.
输入样例#1：
4 5
1 4
2 3
1 5
输出样例#1：
3
2
1
1
题解
这道题的方法到底有多少呢，我也不知道。最常见的应该是倍增+差分吧。
这题我写的左偏树。
考虑每个点只会给他的祖先贡献答案，且满足\(dep_u-dep_v<=L\)（u是当前节点，v是某个祖先节点）。那么当一个点不能给它的某一个祖先v贡献答案时，它将也不能给更上方的祖先贡献答案（废话）。
所以我们把点按\(dep\)值从大到小排序，每次合并自己的子树，最后把\(dep>dep_u+L\)的点弹掉，维护一下\(size\)即可。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 200005;
struct edge{int to,next;ll w;}a[N<<1];
int n,head[N],cnt,ls[N],rs[N],dis[N],sz[N];
ll L,dep[N];
ll gi()
{
ll x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
int Merge(int A,int B)
{
if (!A||!B) return A+B;
if (dep[A]<dep[B]) swap(A,B);
rs[A]=Merge(rs[A],B);
if (dis[ls[A]]<dis[rs[A]]) swap(ls[A],rs[A]);
dis[A]=dis[rs[A]]+1;
return A;
}
int Delete(int A)
{
return Merge(ls[A],rs[A]);
}
int dfs(int u,int fa)
{
int A=u;sz[u]=1;
for (int e=head[u];e;e=a[e].next)
{
int v=a[e].to;if (v==fa) continue;
dep[v]=dep[u]+a[e].w;
A=Merge(A,dfs(v,u));
sz[u]+=sz[v];
}
while (dep[A]-dep[u]>L) sz[u]--,A=Delete(A);
return A;
}
int main()
{
n=gi();L=gi();
for (int u=2;u<=n;u++)
{
int v=gi();ll w=gi();
a[++cnt]=(edge){v,head[u],w};head[u]=cnt;
a[++cnt]=(edge){u,head[v],w};head[v]=cnt;
}
dfs(1,0);
for (int i=1;i<=n;i++)
printf("%d\n",sz[i]);
return 0;
}