bzoj2783 树

第一行是两个整数N和S，其中N是树的节点数。

第二行是N个正整数，第i个整数表示节点i的正整数。

接下来的N-1行每行是2个整数x和y，表示y是x的儿子。

输出格式：

输出路径节点总和为S的路径数量。

输入样例：	输出样例：
3 3 1 2 3 1 2 1 3

数据范围：

对于30%数据，N≤100；

对于60%数据，N≤1000；

对于100%数据，N≤100000，所有权值以及S都不超过1000。

倍增预处理出每个节点向上走2^k步到达的点和权值和，对每个点二分向上能走（权值和小于S）的距离

#include<cstdio>

inline int input(){

    int x=,c=getchar();

    while(c>||c<)c=getchar();

    while(c>&&c<)x=x*+c-,c=getchar();

    return x;

}

const int N=;

int n,S,ans=;

int vs[][N],fa[][N];

int main(){

    n=input();S=input();

    for(int i=;i<=n;i++)vs[][i]=input();

    for(int i=,a,b;i<n;i++){

        a=input();b=input();

        fa[][b]=a;

    }

    for(int t=;t<;t++){

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

            int f=fa[t][i];

            fa[t+][i]=fa[t][f];

            vs[t+][i]=vs[t][f]+vs[t][i];

        }

    }

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

        int s=S,w=i;

        for(int k=;k;k--){

            int f=fa[k][w];

            if(!f)continue;

            if(vs[k][w]<s)s-=vs[k][w],w=f;

        }

        if(s==vs[][w])++ans;

    }

    printf("%d\n",ans);

    return ;

}