题解 P3066 【[USACO12DEC]Running Away From the Barn G】

原文链接

题意很清晰，我们可以用前缀和转化一下，设(u)到根的距离为(dis[u])，则在(u)的子树中满足到(u)的距离不大于(t)的点(v)满足

[dis[v]-dis[u]leq t ]

即

[dis[u]+tgeq dis[v] ]

我们先跑一边(dfs)，每个点的子树就对应一段区间，然后问题就转化成了：求一段区间内小于等于某个数的值有几个，裸的主席树。

然后上板子即可，但细节有点多。

(Code)

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;

struct edge
{
    int v,nxt;
    ll w;
    edge(int v=0,ll w=0,int nxt=0) :v(v),w(w),nxt(nxt){}
}e[maxn<<1];
int lc[maxn<<5],rc[maxn<<5],sum[maxn<<5];
int rt[maxn],tot;
int head[maxn],kt,dfn[maxn],siz[maxn],n,cnt,m,id[maxn];
ll dis[maxn],b[maxn],t;

template<typename T>
inline void read(T &x)
{
    char c;int f=1;
    while(!isdigit(c=getchar())) (c=='-')&&(f=-1);
    x=c^48;
    while(isdigit(c=getchar())) x=x*10+(c^48);
    x*=f;
}

inline void add(int u,int v,ll w)
{
    e[++kt] = edge(v, w, head[u]);
    head[u] = kt;
}

void dfs(int u,int fa,ll ds)
{
    dis[u] = ds;siz[u] = 1;
    dfn[u] = ++cnt;id[cnt]=u;
    for (int i = head[u];i;i=e[i].nxt)
        if(e[i].v!=fa) {
            dfs(e[i].v, u, ds + e[i].w);
            siz[u] += siz[e[i].v];
        }
}

void build(int &u,int l,int r)
{
    u=++tot;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lc[u],l,mid);build(rc[u],mid+1,r);
}

void insert(int &u,int pre,int l,int r,int x)
{
    u=++tot;lc[u]=lc[pre];rc[u]=rc[pre];sum[u]=sum[pre]+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(x<=mid) insert(lc[u],lc[pre],l,mid,x);
    else insert(rc[u],rc[pre],mid+1,r,x);
}

int query(int u,int v,int l,int r,int x,int y)
{
    if(r<x||l>y) return 0;
    if(x<=l&&r<=y) return sum[v]-sum[u];
    int mid=(l+r)>>1;
    return query(rc[u],rc[v],mid+1,r,x,y)+query(lc[u],lc[v],l,mid,x,y);
}

int main()
{
    int u;
    ll w;
    read(n);read(t);
    for (int i=2;i<=n;++i)
    {
        read(u);read(w);
        add(i,u,w);add(u,i,w);
    }
    dfs(1,0,0);
    for(int i=1;i<=n;++i) b[i]=dis[i];
    sort(b+1,b+n+1);b[n+1]=1e18;
    m=unique(b+1,b+n+2)-b-1;
    build(rt[0],1,m);
    for(int i=1;i<=n;++i)
        insert(rt[i],rt[i-1],1,m,lower_bound(b+1,b+m+1,dis[id[i]])-b);
    for(int i=1;i<=n;++i)
    {
        int x=lower_bound(b+1,b+m+1,dis[i])-b-1,y=lower_bound(b+1,b+m+1,dis[i]+t)-b-1;
        if(b[x+1]==dis[i]) ++x;if(b[y+1]==dis[i]+t) ++y;
        if(y==m-1) printf("%d
",siz[i]); 
        else printf("%d
",query(rt[dfn[i]-1],rt[dfn[i]+siz[i]-1],1,m,x,y));
    }
    return 0;
}