P3252 [JLOI2012]树

陈020321_victor · 2018-07-27 19:53:17 · 个人记录

题目描述 在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路径不必一定从根节点开始。

输入输出格式 输入格式： 第一行是两个整数N和S，其中N是树的节点数。 第二行是N个正整数，第i个整数表示节点i的正整数。 接下来的N-1行每行是2个整数x和y，表示y是x的儿子。

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

输入输出样例 输入样例#1： 3 3 1 2 3 1 2 1 3 输出样例#1： 2 说明 对于100%数据，N<=100000，所有权值以及S都不超过1000。

本题思路解析：这里是一个树上前缀和求区间的题。看到区间求和应该能反映出前缀和这个东西，可以大大加快速率。而且本题也满足前缀和的性质，因为一定是一条链上的区间求和，所以直接便利节点的每个父亲，利用前缀和的可减性就可以了。注意如果满足要求或超过要求要剪枝

上代码

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int v,next;
} e[200005];
int pre[100005],head[100005],tot=0,fa[100005],w[100005],n,s,ans = 0;
void addedge(int x,int y){
    e[++tot].v = y;
    e[tot].next = head[x];
    head[x] = tot;
}
void dfs(int u,int las){
    fa[u] = las;
    pre[u] = pre[las] + w[u];
    int p = fa[u];
    while(p){
        if(pre[u]-pre[p]==s) ans++;
        if(pre[u]-pre[p]>s) break;//剪枝在这里
        p = fa[p];
    }
    if(pre[u]==s) ans++;
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].v;
        if(v==las) continue;
        dfs(v,u);
    }
}
int main(){
    std::cin.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1,a,b;i<n;i++){
        cin>>a>>b;
        addedge(a,b);addedge(b,a);
    }
    dfs(1,0);
    printf("%d",ans);
}