[JLOI2012] 树
2024-08-24 09:02:22
Description
在这个问题中,给定一个值S和一棵树。在树的每个节点有一个正整数,问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点,根的深度是0,它的儿子节点的深度为1。路径不必一定从根节点开始。
Input
第一行是两个整数N和S,其中N是树的节点数。 第二行是N个正整数,第i个整数表示节点i的正整数。 接下来的N-1行每行是2个整数x和y,表示y是x的儿子。
Output
输出路径节点总和为S的路径数量。
Range
对于100%数据,N<=100000,所有权值以及S都不超过1000。
Solution
转化一下题意,就是求树上的一条链,使权值之和等于s。
我们可以利用dfs求出树上每个点到根的权值和(也就是树上的前缀和),在回溯的过程中求出答案即可。
具体做法是,当我们在搜一个点 i 时,看一眼有没有它的某个祖先 j 使得 qzh[j]-qzh[i]=p
如何找这个祖先呢?我们可以用 STL 中的 set ,在 dfs 的时候将当前点的前缀和插进集合,回溯的时候找集合中是否有值为 p-qzh[now] 的点,如果有,代表它的某个祖先到它即为一条合法路径, ans++,回溯最后记得从集合中 erase 掉 qzh[now] 即可。
Code
#include<set> #include<cstdio> #define N 100005 #define int long long using namespace std; int ans; set<int> s; int head[N]; int is_root[N]; int val[N],qzh[N]; ; struct Edge{ int to,nxt; }edge[]; void add(int x,int y){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt; } void dfs(int now,int fa){ for(int i=head[now];i;i=edge[i].nxt){ if(edge[i].to==fa) continue; s.insert(qzh[now]); qzh[edge[i].to]=qzh[now]+val[edge[i].to]; dfs(edge[i].to,now); int k=qzh[edge[i].to]-p; if(s.count(k)) ans++; s.erase(qzh[edge[i].to]); } } signed main(){ scanf("%lld%lld",&n,&p); ;i<=n;i++) scanf("%lld",&val[i]); ;i<n;i++){ scanf("%lld%lld",&x,&y); add(x,y);add(y,x); } s.insert(); qzh[]=val[]; dfs(,); printf("%lld",ans); ; }
最新文章
- 关于Web服务器的认识
- ps图像渐变
- Scala学习笔记(六):Scala程序
- Linux Shell远程执行命令(命令行与脚本方式)
- java程序执行内存处理过程
- hibernate一对多关联关系
- quick 2.23 它们的定义c++代码lua与总结的一些细节
- 练习markdown语法
- c++单链表冒泡排序(交换结点),链表增删改查,运算符重载
- Edusoho之LAMP环境搭建
- HDU 6400(括号组合 ~)
- Linux命令行快捷键及vim快捷方式
- C++11--右值引用(移动语义)
- Netty入门(六)Decoder(解码器)
- DXT 图片压缩(DXTC/DirectX Texture Compression Overview)
- eclipse下JAVA的搭建
- window安装ubuntu系统
- 《java并发编程实战》读书笔记8--死锁,性能与可伸缩性,锁粒度锁分解锁分段
- ARC075 F.Mirrored
- python连接数据库--查询数据
热门文章
- HttpClient调用RestFul接口(post和get方式)
- OpenGL直线点画模式
- Caused by: com.mysql.jdbc.MysqlDataTruncation: Data truncation: Truncated incorrect DOUBLE value: &#39;L
- CentOS中配置NFS服务
- 翻译--Thinking in React
- UltraEdit 脚本 实现查找替换
- C#图解教程 第六章 深入理解类
- PyTorch官方中文文档:torch
- 【小白学爬虫连载(10)】–如何用Python实现模拟登陆网站
- 【BZOJ2006】超级钢琴(主席树,优先队列)