P3066 [USACO12DEC] 逃跑的Barn 左偏树

P3066 逃跑的Barn 左偏树

题面

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

注意到答案的两个性质：

• 一个点的所有答案一定包含在其所有儿子的答案中
• 如果节点\(i​\)当前满足条件，那么所有距离（相对于根节点）比它小的节点当前也都满足（所以建个大根堆）

所以考虑使用左偏树，每个节点都建个大根堆，在\(dfs\)时计算出所有点深度，再利用这些性质回溯时依次合并所有堆，显然答案即为堆的大小。

注意long long卡了我好久

#include <cstdio>

#include <algorithm>

#define MAXN 200002

#define LL long long

using namespace std;

int n;long long l;

int head[MAXN],nxt[MAXN*2],vv[MAXN*2],tot;

LL ww[MAXN*2];

inline void add_edge(int u, int v, LL w){

    ww[++tot]=w;

    vv[tot]=v;

    nxt[tot]=head[u];

    head[u]=tot;

}

LL val[MAXN];

int root[MAXN],sz[MAXN],sl[MAXN],sr[MAXN],dis[MAXN];

int merge(int a, int b){

    if(a==0||b==0) return a+b;

    if(val[a]<val[b]) swap(a,b);

    sr[a]=merge(sr[a], b);

    if(dis[sl[a]]<dis[sr[a]]) swap(sl[a], sr[a]);

    dis[a]=dis[sr[a]]+1;

    return a;

}

void dfs(int u, LL wnow){

    root[u]=u;

    val[u]=wnow;

    sz[u]=1;

    for(int i=head[u];i;i=nxt[i]){

        int v=vv[i];

        LL w=ww[i];

        dfs(v, wnow+w);

        root[u]=merge(root[u], root[v]);

        sz[u]+=sz[v];

        while(val[root[u]]-val[u]>l){

            root[u]=merge(sl[root[u]], sr[root[u]]);

            sz[u]--;

        }

    }

}

int main()

{

    scanf("%d %lld", &n, &l);

    for(int i=2;i<=n;++i){

        int fa;LL w;

        scanf("%d %lld", &fa, &w);

        add_edge(fa,i,w);

    }

    dfs(1,0);

    for(int i=1;i<=n;++i)

        printf("%d\n", sz[i]);

    return 0;

}