P3252 [JLOI2012]树

题目描述

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

输入格式

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

输出格式

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

简单的思路就是先构造一棵树，然后便利树，因为深度要递增，所以我们要从一个点不断的去找叶子节点。

链式前向星存图

 struct  node

 {

     int w;//代表这条边的边权数值；

     int e;//代表以这条边为结尾的点的下标值;

     int next;//表示与第i条边同起点的上一条边的存储位置

 }ed[maxn];

 int head [maxn];//用来存储边的位置

 int tot =;

 void add (int u,int v,int w)

     {

       ed[++tot].w=w;//表示第i条边的权职是多少

       ed[tot].e=v;//表示第i条边的终点

       ed[tot].next=head[u];//head[i]表示以i为起点最后一条边的存储位置

       head[u]=tot++;

 }

因为这道题不涉及到权值的问题，所以我们就不作考虑。

那这道题的链前就可以写为：

 struct node

 {

     int u;

     int v;

 }to[];

 void add(int x,int y)

 {

     to[++tot].u=head[x];//head[i]表示以i为起点最后一条边的存储位置

     to[tot].v=y;//表示i条边的终点，也就是所连的节点

     head[x]=tot;//一共所连的边数

 }

遍历一棵树可以用dfs但是由于这道题的数据范围，我们还需要再加一个剪枝。

如果当前节点和已经超过s，我们就不需要继续往下搜索了。

搜索的时候，深度需要升序，我们只能往下找当前节点的子节点。

但是这样还不够，就即使加了剪枝依然会t掉4个点，所以我加了一个小小的读入优化，就神奇的过辽！

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int a[];

 int st,ed;

 int read()

 {

     int x = ,a = ;

     char ch = getchar();

     while(ch < '' || ch > ''){

         if(ch == '-')x = -;

         ch = getchar();

     }

     while(ch <= ''&&ch >= ''){

         a = a *  + ch - '';

         ch = getchar();

     }

     return x*a;

 }

 struct node

 {

     int u;

     int v;

 }to[];

 int fa[],head[],x,y,n,s,tot=,ans=;

 void add(int x,int y)

 {

     to[++tot].u=head[x];

     to[tot].v=y;

     head[x]=tot;

 }

 void dfs(int x,int dis)

 {

     if (dis>s)

         return;

     if (dis==s)

     {

         ans++;

         return;

     }

     for (int i = head[x];i>;i=to[i].u)

     {

         int nxt=to[i].v;

         if (fa[x]!=nxt)

             dfs(nxt,dis+a[nxt]);

     }

 }

 int main()

 {

     n = read();

     s = read();

     memset(head, -, sizeof(head));

     for (int i = ;i <= n;i++)

     {

         a[i] = read();

         fa[a[i]]=a[i];

     }

     for (int i = ;i <= n-;i++)

     {

         st=read();

         ed=read();

         add(st,ed);

         fa[ed]=st;

     }

     for (int i = ;i <= n;i++)

     {

         dfs(i,a[i]);

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

P3252 [JLOI2012]树

题目描述

输入格式

输出格式

最新文章

热门文章