C. Kefa and Park

悠悠 2021-12-03 23:25 206阅读 0赞

题目链接：[http://codeforces.com/problemset/problem/580/C][http_codeforces.com_problemset_problem_580_C]

题目大意：给定一棵 N 个节点的有根树（其中根节点始终为 1 号节点），点有点权，点权只有 1 和 0 两种，求从根节点到叶子节点的路径中，有多少条路径满足：路径上最大连续点权为 1 的节点个数不超过 M。

自己一开始一直理解错了题意！ 哭泣！

做过这道题以后，遇到有限制条件的搜索自己应该知道该如何去写了！！

AC代码：

1 #include <cstdio>
     2 #include <string>
     3 #include <iostream>
     4 #include <algorithm>
     5 #include <string.h>
     6 #include <math.h>
     7 #include <vector>
     8  
     9 using namespace std;
    10  
    11  
    12 const int len=1e5+3;
    13 const int INF=0x3f3f3f3f;
    14 #define ll long long
    15 const ll mod=1e18;
    16  
    17 struct Node{
    18     vector<int>ve;
    19     int f;
    20 }node[len];
    21 ll ans;
    22 int n,m;
    23 int vis[len];
    24 void dfs(int r,int sum)
    25 {
    26     if(sum>m)return ; // 判断猫的数目
    27     if(node[r].ve.size()==1&&vis[node[r].ve[0]])//判断是否是叶子节点
    28     {
    29         ans++;
    30         return ;
    31     }
    32     for(int i=0;i<node[r].ve.size();++i)
    33     {
    34         int t=node[r].ve[i];
    35         if(vis[t])continue;
    36         vis[t]=1;
    37         if(node[t].f==0)dfs(t,0);
    38         else dfs(t,sum+1);
    39     }
    40 }
    41 int main()
    42 {
    43     cin>>n>>m;
    44     for(int i=1;i<=n;++i)
    45         scanf("%d",&node[i].f);
    46     int u,v;
    47     for(int i=0;i<n-1;++i)
    48     {
    49         scanf("%d%d",&u,&v);
    50         node[u].ve.push_back(v);
    51         node[v].ve.push_back(u);
    52     }
    53     vis[1]=1;
    54     dfs(1,node[1].f);
    55     cout<<ans<<endl;
    56     return 0;
    57 }

转载于:https://www.cnblogs.com/-Ackerman/p/11173619.html

[http_codeforces.com_problemset_problem_580_C]: http://codeforces.com/problemset/problem/580/C