[USACO 12DEC]Running Away From the Barn

Description

It's milking time at Farmer John's farm, but the cows have all run away! Farmer John needs to round them all up, and needs your help in the search.

FJ's farm is a series of N (1 <= N <= 200,000) pastures numbered 1...N connected by N - 1 bidirectional paths. The barn is located at pasture 1, and it is possible to reach any pasture from the barn.

FJ's cows were in their pastures this morning, but who knows where they ran to by now. FJ does know that the cows only run away from the barn, and they are too lazy to run a distance of more than L. For every pasture, FJ wants to know how many different pastures cows starting in that pasture could have ended up in.

Note: 64-bit integers (int64 in Pascal, long long in C/C++ and long in Java) are needed to store the distance values.

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

Input

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.

Output

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.

Sample Input

Sample Output

Hint

Cows from pasture 1 can hide at pastures 1, 2, and 4.

Cows from pasture 2 can hide at pastures 2 and 3.

Pasture 3 and 4 are as far from the barn as possible, and the cows can hide there.

题解

简要来说，左偏树

具体思想是：先$Dfs$求出根节点到各个节点的距离，再按逆$Dfs$时间戳顺序进行操作（为了使得处理的当前节点的所有子节点均被处理过，至于为何不正向，就不解释了）

建大根堆，每次做完合并操作后，将不可行的边从堆中弹出（即堆顶所表示的点到当前点的距离$>L$（同时以操作顺序为前提的条件下必有“相距距离=两点到根节点的距离差”））

另一个需要解决的问题就是如何求解，我们可以按逆$Dfs$序模拟一个回溯过程：将所以$pop$掉的值和其子节点的值累加，再相减即可。

 1 #include<cmath>
 2 #include<queue>
 3 #include<stack>
 4 #include<ctime>
 5 #include<cstdio>
 6 #include<string>
 7 #include<cstdlib>
 8 #include<iostream>
 9 #include<algorithm>
10  using namespace std;
11 const long long N=200000;
12 struct tt
13 {
14     long long cost,next,to;
15 }edge[2*N+5];//保存边的信息 
16 long long path[N+5],top;
17 struct node
18 {
19     long long key,dist;
20     node *l,*r;
21     long long ldist() {return l ? l->dist:-1;}
22     long long rdist() {return r ? r->dist:-1;}
23 }T[N+5],*root[N+5];//T[i]表示节点i的相关信息;root[i]表示序号为i的节点所在堆的根的地址 
24 long long n,l,a,b;
25 long long remain[N+5],tail,Rank[N+5];//remain[]表示逆Dfs顺序,tail表示remain[]的大小;Rank[]表示Bfs序 
26 long long popnum[N+5],cnt[N+5];//popnum[i]保存在i节点时,弹出元素的数量 cnt[i]表示以i为根，其子树节点数量(不含根节点) 
27 void Add(long long x,long long y,long long cost);
28 void Dfs(long long x);
29 node* Merge(node* a,node* b);
30 int main()
31 {
32     scanf("%lld%lld",&n,&l);
33     for (long long i=2;i<=n;i++)
34     {
35         scanf("%lld%lld",&a,&b);
36         Add(a,i,b);
37         Add(i,a,b);
38 
39 }//连双向边,正向用于Dfs用,逆向用于求解用
40 
41     Rank[1]=1;
42     Dfs(1);
43     for (long long i=1;i<=tail;i++) 
44     {
45         for (long long j=path[remain[i]];j;j=edge[j].next)
46         {
47             if (Rank[remain[i]]==Rank[edge[j].to]+1)//找到前驱节点 
48             {
49                 root[edge[j].to]=Merge(root[remain[i]],root[edge[j].to]);//将当前节点构成的堆并入前驱节点 
50                 while(root[edge[j].to]->key-T[edge[j].to].key>l)//弹出 
51                 {
52                     popnum[edge[j].to]++;
53                     root[edge[j].to]=Merge(root[edge[j].to]->l,root[edge[j].to]->r);
54                 }
55             }
56         }
57     }
58     for (long long i=1;i<=tail;i++) //对最终答案数据的处理 
59     {
60         for (long long j=path[remain[i]];j;j=edge[j].next)
61         {
62             if (Rank[remain[i]]==Rank[edge[j].to]+1)
63             {
64                 cnt[edge[j].to]+=cnt[remain[i]]+1;
65                 popnum[edge[j].to]+=popnum[remain[i]];
66             }
67         }
68     }
69     for (long long i=1;i<=n;i++) printf("%lld
",cnt[i]+1-popnum[i]);
70     return 0;
71 }
72 void Add(long long x,long long y,long long cost)
73 {
74     edge[++top].to=y;
75     edge[top].cost=cost;
76     edge[top].next=path[x];
77     path[x]=top;
78 }
79 void Dfs(long long x)
80 {
81     root[x]=x+T;
82     for (long long i=path[x];i;i=edge[i].next) if (!Rank[edge[i].to])
83     {
84         Rank[edge[i].to]=Rank[x]+1;
85         T[edge[i].to].key=T[x].key+edge[i].cost;//key保存的是根节点到该点的距离 
86         Dfs(edge[i].to);
87     }
88     remain[++tail]=x;
89 }
90 node* Merge(node* a,node* b)
91 {
92     if (!a||!b) return a ? a:b;
93     if (a->key<b->key) swap(a,b);
94     a->r=Merge(a->r,b);
95     if (a->ldist()<a->rdist()) swap(a->l,a->r);
96     a->dist=a->rdist()+1;
97     return a;
98 }