Luogu

分析

$O(n)$计算树上前缀和，然后每个节点往上爬，枚举链即可。

卡个常就能氵过去。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#define re register
using namespace std;
struct node //节点
{
    int d,sonsum,fa;
    vector<int> son;
    int sum;
    node()
    {
        this->d=this->sum=this->sonsum=this->fa=0;
        this->son.clear();
    }
}a[100010];
int n,s,ans;
inline void Make() //建树
{
    int u,v;
    scanf("%d%d",&n,&s);
    for (re int i=1;i<=n;i++) { scanf("%d",&a[i].d); a[i].son.push_back(0); }
    for (re int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        a[u].sonsum++; a[u].son.push_back(v);
        a[v].fa=u;
    }
}
inline void Dfs(int k) //搜索
{
    a[k].sum=a[a[k].fa].sum+a[k].d; //计算前缀和
    int now=a[k].fa;
    if (a[k].sum==s) ans++; //特判到根节点路径
    while (now) //枚举祖先
    {
        if (a[k].sum-a[now].sum==s) ans++;
        if (a[k].sum-a[now].sum>=s) break; //如果大了就直接break，因为权值都为正
        now=a[now].fa;
    }
    for (re int i=1;i<=a[k].sonsum;i++) Dfs(a[k].son[i]); //搜索子节点
}
int main()
{
    Make();
    Dfs(1);
    printf("%d\n",ans);
    return 0;
}