逃离牧场

时间限制: 3 Sec 内存限制: 128 MB

题目描述

约翰有 N 片牧场，以 1 到 N 编号，每个牧场里都住着奶牛。牧场之间有 N −1 条双向通行的道

路，约翰的家在 1 号牧场，所有牧场都和他家连通。

有一天，约翰的奶牛集体大逃亡了！奶牛在逃亡的时候，总是选择远离约翰家的方向行动的。当

i > 1 时，牧场 i 的所有邻居中，只有一个牧场距离 1 号牧场是更近的，记这个牧场的编号为 P i ，记

i 和 P i 之间道路的距离为 L i 。奶牛的运动能力不足，所有奶牛在逃亡的过程中，行走不超过 K 公里

就会停下来，有些奶牛甚至可能根本就没走过一步！请你帮助约翰分别计算一下，对每个原本住在牧

场 i 里的奶牛，可能逃亡到多少个牧场。

输入

• 第一行：两个整数 N 和 L，1 ≤ N ≤ 200000, 1 ≤ L ≤ 10 18

• 第二行到第 N 行：第 i + 1 行有两个整数 P i 和 L i ，1 ≤ P i < i, 1 ≤ L i ≤ 10 12

输出

• 第 1 行到第 N 行：第 i 行输出住在牧场 i 里的奶牛可能逃亡到多少个牧场。

样例输入

4 5

1 4

2 3

1 5

样例输出

提示

住在 1 号的可能逃到 1,2,4

住在 2 号的可能逃到 2,3

住在 3 号和 4 号的没有其他地方可去

题解：

垃圾的左偏树裸题。

先用SPFA处理出某点到根节点的距离。（任何两点间的距离都可以用dist[i]-dist[j]表示）

建立大根堆保存以当前节点为根节点的子树中符合题目要求的点到根节点的距离。

从叶子节点到根节点遍历，不断合并节点。

以下是AC代码：（虽丑无碍）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
using namespace std;
int n;
long long m;
struct node
{
    long long key;
    int dist;
    node *l,*r;
    int ldist(){return l?l->dist:0;}
    int rdist(){return r?r->dist:0;}
}cow[200005];
node *pos=cow,*root[200005];
struct student
{
    int next,to;
    long long dis;
}edge[500005];
int size,head[200005],father[200005],cnt[200005],num[200005];
long long dist[200005];
void putin(int from,int to,long long dis)
{
    size++;
    edge[size].next=head[from];
    edge[size].to=to;
    edge[size].dis=dis;
    head[from]=size;
}
void bfs()
{
    int i,j;
    queue<int>p;
    p.push(1);
    while(!p.empty())
    {
        int x=p.front();
        p.pop();
        for(i=head[x];i!=-1;i=edge[i].next)
        {
            int y=edge[i].to;
            if(y!=father[x]&&!dist[y])
            {
                dist[y]=dist[x]+edge[i].dis;
                p.push(y);
            }
        }
    }
    return;
}
queue<int>mem;
void newnode(int x,long long dis)
{
    pos++;
    root[x]=pos;
    root[x]->key=dis;
    num[x]=1;
    root[x]->l=root[x]->r=NULL;
}
node* merge(node *a,node *b)
{
    if(!a||!b)return a?a:b;
    if(a->key<b->key)swap(a,b);
    a->r=merge(a->r,b);
    if(a->ldist()<a->rdist())swap(a->l,a->r);
    a->dist=a->rdist()+1;
    return a;
}
void delet(int x)
{
    num[x]--;
    root[x]=merge(root[x]->l,root[x]->r);
}
int main()
{
    int i,j;
    scanf("%d%lld",&n,&m);
    memset(head,-1,sizeof(head));
    for(i=2;i<=n;i++)
    {
        long long dis;
        scanf("%d%lld",&father[i],&dis);
        cnt[father[i]]++;
        putin(father[i],i,dis);
        putin(i,father[i],dis);
    }
    bfs();
    for(i=1;i<=n;i++)
    {
        newnode(i,dist[i]);
        if(!cnt[i])mem.push(i);
    }
    while(!mem.empty())
    {
        int x=mem.front();
        mem.pop();
        int fa=father[x];
        root[fa]=merge(root[fa],root[x]);
        num[fa]+=num[x];
        cnt[fa]--;
        if(!cnt[fa])
        {
            while(abs(root[fa]->key-dist[fa])>m)delet(fa);
            mem.push(fa);
        }
    }
    for(i=1;i<=n;i++)
    printf("%d
",num[i]);
    return 0;
}