题解[JLOI2012]树

题目：
P3252 [JLOI2012]树

比较巧妙地统计路径长度。直接用g[i][j-1],g[f[i][j-1]][j-1]去计算当前路径的长度。

然后就像找lca一样每次往上跳，不过不是二进制分解是统计长度。

#include<cstdio>
#define it register int
#define il inline
const int N=1000005;
int f[N][20],g[N][20],n,s,ans;
il void fr(int &num){
    num=0;char c=getchar();int p=1;
    while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    num*=p;
}
int main(){
    fr(n),fr(s);
    it u,v;
    for(it i=1;i<=n;++i) fr(g[i][0]);
    for(it i=1;i<n;++i) fr(u),fr(v),f[v][0]=u;
    for(it j=1;j<=17;++j)
        for(it i=1;i<=n;++i)
            f[i][j]=f[f[i][j-1]][j-1],g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1]; 
    for(it i=1;i<=n;++i){
        u=i,v=0;
        for(it j=17;v<s&&j>=0;--j)
            if(g[u][j]+v<=s) v+=g[u][j],u=f[u][j];
        ans+=(v==s);
    }
    printf("%d",ans); 
    return 0;
}