关键词：

3 3
1 2 3
1 2
1 3

2

#include<iostream>
#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100100
using namespace std;
set<int>se;
int n,s,tot,ans;
int sum[MAXN],w[MAXN],dad[MAXN];
int to[MAXN*2],head[MAXN*2],net[MAXN*2];
void add(int u,int v){
    to[++tot]=v;net[tot]=head[u];head[u]=tot;
}
void dfs(int now){
    sum[now]=sum[dad[now]]+w[now];
    se.insert(sum[now]);
    if(se.find(sum[now]-s)!=se.end())    ans++;
    for(int i=head[now];i;i=net[i])    dfs(to[i]);
    se.erase(sum[now]);
}
int main(){
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        dad[y]=x;
        add(x,y);
    }
    se.insert(0);
    dfs(1);
    cout<<ans;
}

题解p3252[jloi2012]树(代码片段)

(Huge[JLOI2012]树)题目描述在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路... 查看详情

p3252[jloi2012]树(代码片段)

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

洛谷p3884[jloi2009]二叉树问题(代码片段)

题目描述如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：深度：4宽度：4（同一层最多结点个数）结点间距离：⑧→⑥为8(3×2+2=8)⑥→⑦为3（1×2+1=3）注：结点间距离的定义：由结点向根方向（上行方向... 查看详情

bzoj2783[jloi2012]树

题解：set就好#include<iostream>#include<cstdio>#include<map>#include<cstring>usingnamespacestd;constintmaxn=100009;intn,k;introot;intw[maxn];intnotroot[maxn];intans;intcntedge;inthe 查看详情

bzoj2783[jloi2012]树dfs+栈+队列

【BZOJ2783】[JLOI2012]树Description    在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的... 查看详情

bzoj2783[jloi2012]树

Description数列提交文件：sequence.pas/c/cpp输入文件：sequence.in输出文件：sequence.out问题描述：把一个正整数分成一列连续的正整数之和。这个数列必须包含至少两个正整数。你需要求出这个数列的最小长度。如果这个数列不存在则... 查看详情

[bzoj2783][jloi2012]树_树的遍历

树bzoj2783JLOI2012题目大意：给定一棵n个点的树。求满足条件的路径条数。说一个路径是满足条件的，当且仅当这条路径上每个节点深度依次递增且点权和为S。注释：$1lenle10^5$，$1leS,val_ile10^3$。想法：翻lijinnn的blog翻到的水题。我... 查看详情

[jloi2012]树

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

「jloi2012」树(代码片段)

「JLOI2012」树传送门不得不说这题的数据是真的水。。。我们可以想到很明确的一条思路：枚举每一个点向根节点跳，知道路径和不小于(s)，恰好等于(s)就直接加答案。跳的过程可以用倍增搞，但是暴力跳也可以过（这棵树的高... 查看详情

[luogup3252][jloi2012]树（dp）

传送门 树上前缀和。在树上找一条权值和为s的链，其中这个链上的点按深度递增（递减）（不同）dfs每搜到一个点求它的前缀和sum[x]，放入set中。在set中找sum[x]-s的点，如果有，ans++退出dfs的时候再把sum[x]从set中删除因为每... 查看详情

洛谷lca+树上差分p3258[jloi2014]松鼠的新家(代码片段)

【题目描述：】松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n(2≤n ≤300000)个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。松... 查看详情

搜索练习2

P3252[JLOI2012]树题目描述　　在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1... 查看详情

洛谷3833shoi2012魔法树

【题解】　　树链剖分模板题。。#include<cstdio>#include<algorithm>#include<queue>#defineN500010#definergregister#definels(u<<1)#definers(u<<1|1)#definemid((a[u].l+a[u].r)>>1)#defin 查看详情

洛谷p3253[jloi2013]删除物品解题报告(代码片段)

P3253[JLOI2013]删除物品题目描述箱子再分配问题需要解决如下问题：（1）一共有\(N\)个物品，堆成\(M\)堆。（2）所有物品都是一样的，但是它们有不同的优先级。（3）你只能够移动某堆中位于顶端的物品。（4）你可以把任意一堆... 查看详情

bzoj2830&洛谷3830：[shoi2012]随机树——题解(代码片段)

https://www.luogu.org/problemnew/show/P3830#sub  <-题面看这里~https://www.lydsy.com/JudgeOnline/problem.php?id=2830感觉智商被压制了的一题……后面放吐槽。参考：https://www.cnblogs.com/GuessYCB/p/846249 查看详情

洛谷3830[shoi2012]随机树概率dp(代码片段)

题目输入格式输入仅有一行，包含两个正整数q,n，分别表示问题编号以及叶结点的个数。输出格式输出仅有一行，包含一个实数d，四舍五入精确到小数点后6位。如果q=1，则d表示叶结点平均深度的数学期望值；如果q=2，则d表示... 查看详情

[洛谷p3261][jloi2015]城池攻占(左偏树)(代码片段)

不得不说，这道题目是真的难，真不愧它的“省选/NOI-”的紫色大火题！！！花了我晚自习前半节课看题解，写代码，又花了我半节晚自习调代码，真的心态爆炸。基本上改得和题解完全一样了我才过了这道题！真的烦。没事，... 查看详情

bzoj4006[jloi2015]管道连接（斯坦纳树+dp）(代码片段)

题目链接题意：给出(n)个点，(m)条边，同时给出(p)个重要的点以及对应特征。现在要选出一些边，问使得这(p)个所有特征相同的点相连，问最小代价。思路：斯坦纳树的应用场景一般就为：使得一些点连通，在此基础上，允许连... 查看详情