Description
在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路径不必一定从根节点开始。解题报告： 用时20min，1AC 这题找到了题面就简单了，因为题目要求路径深度要满足升序，所以直接把一个点的所有的父节点都压人栈中，然后二分到那个位置，如果存在这样的路径答案就加1
#include#include #include #include #include #include #define RG register#define il inline#define iter iterator#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std;const int N=100005;int head[N],num=0,S,nxt[N<<1],to[N<<1],val[N],n,st[N],top=0,dis[N];void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}bool check(int x){ int l=0,r=top,mid; while(l<=r){ mid=(l+r)>>1; if(dis[x]-dis[st[mid]]==S)return true; if(dis[x]-dis[st[mid]]