P3066 [USACO12DEC] Running Away From the Barn G——树上差分+树上倍增

· · 个人记录

因为一个父亲往往对应着多个儿子，而一个儿子只对应一个父亲

考虑对于每一个节点u，记录它对每一个祖先节点的贡献

可以发现每条边的边权为正数，也就是说一个点到其深度越浅的祖先的路径长度必然是单调递增的

同时这也可以说明每个节点对其祖先的有贡献的范围必然是一条连续的链

考虑使用树上差分

这个时候就只需要找对于u而言最后一个距离\le t的祖先

因为满足单调性，考虑二分，但是在树上的话类似的倍增更好实现

时间复杂度O(n \log n)

AC Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll MAXN=2e5+5;

ll fa[MAXN][20],dis[MAXN][20],dep[MAXN];
vector<ll> son[MAXN];

ll delta[MAXN];

ll n,t;

void dfs(ll x){
    dep[x]=dep[fa[x][0]]+1;
    for(ll i=1;(1<<i)<=dep[x];++i){
        fa[x][i]=fa[fa[x][i-1]][i-1];
        dis[x][i]=dis[x][i-1]+dis[fa[x][i-1]][i-1];
    }

    for(auto v:son[x])
        dfs(v);

    ll now=x,sum=0;
    for(ll i=19;i>=0;--i){
        if(!dis[now][i]) continue;
        if(sum+dis[now][i]<=t){
            sum+=dis[now][i];
            now=fa[now][i];
        }
    }
    delta[x]++;delta[fa[now][0]]--;
}//

ll ans[MAXN];

void dfs2(ll x){
    for(auto v:son[x]){
        dfs2(v);
        ans[x]+=ans[v];
    }

    ans[x]+=delta[x];
}//

void work(){
    scanf("%lld%lld",&n,&t);

    for(ll i=2;i<=n;++i){
        scanf("%lld%lld",&fa[i][0],&dis[i][0]);
        son[fa[i][0]].push_back(i);
    }

    dfs(1);
    dfs2(1);

    for(ll i=1;i<=n;++i)
        printf("%lld\n",ans[i]);
}//

int main(){
    work();
    return 0;
}

是哪个神人调了半天最后发现是倍增数组越界啊（恼）