[JLOI 2012]树-白红宇

[JLOI 2012]树

阅读量：5067 次

发布时间：2019-06-12

本文共 1969 字，大约阅读时间需要 6 分钟。

Description

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

Input

第一行是两个整数N和S，其中N是树的节点数。

第二行是N个正整数，第i个整数表示节点i的正整数。

接下来的N-1行每行是2个整数x和y，表示y是x的儿子。

Output

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

Sample Input

3 3

1 2 3

1 2

1 3

Sample Output

HINT

对于100%数据，N≤100000，所有权值以及S都不超过1000。

题解

遍历一遍，将根到当前节点路径上的所有的点的树上前缀和压入栈中。

查找时二分栈即可。

1 //It is made by Awson on 2017.9.29 2 #include 
      
        3 #include 
        4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #define LL long long16 #define Max(a, b) ((a) > (b) ? (a) : (b))17 #define Min(a, b) ((a) < (b) ? (a) : (b))18 #define sqr(x) ((x)*(x))19 #define lowbit(x) ((x)&(-(x)))20 using namespace std;21 const int N = 100000;22 void read(int &x) {23 char ch; bool flag = 0;24 for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());25 for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());26 x *= 1-2*flag;27 }28 29 int n, s, u, v;30 int val[N+5];31 int sum[N+5], top;32 struct tt {33 int to, next;34 }edge[N+5];35 int path[N+5], tot;36 int ans;37 38 void add(int u, int v) {39 edge[++tot].to = v;40 edge[tot].next = path[u];41 path[u] = tot;42 }43 bool erge(int l, int r) {44 while (l <= r) {45 int mid = (l+r)>>1;46 if (sum[top]-sum[mid] == s) return true;47 if (sum[top]-sum[mid] > s) l = mid+1;48 else r = mid-1;49 }50 return false;51 }52 void dfs(int u) {53 sum[++top] = sum[top-1]+val[u];54 ans += erge(0, top);55 for (int i = path[u]; i; i = edge[i].next)56 dfs(edge[i].to);57 top--;58 }59 void work() {60 read(n), read(s);61 for (int i = 1; i <= n; i++) read(val[i]);62 for (int i = 1; i < n; i++)63 read(u), read(v), add(u, v);64 dfs(1);65 printf("%d\n", ans);66 }67 int main() {68 work();69 return 0;70 }

转载于:https://www.cnblogs.com/NaVi-Awson/p/7609498.html

你可能感兴趣的文章

Azure Site Recovery 通过一键式流程将虚拟机故障转移至 Azure虚拟机