CF580C Kefa and Park题解

· · 题解

第一次交题解

已经加了空格，改正了错误，第一次交题解，望通过 QwQ（希望中考前能过一篇）。

题目地址

我看楼下的大佬没用 vector 写的，所以我来水一篇

我先介绍一下 vector 的用法，会的大佬请略过

vector 的优势

vector 是动态数组，你可以用多少开多少，所以他的空间很小，大家学图的时候肯定学过邻接矩阵，那个矩阵很好写，也很好理解，但是因为空间复杂度太高所以会学邻接表，但是那个玩意不如邻接矩阵好理解，容易出错（对于我），但是 vector 能集中邻接表的优势和邻接矩阵的优势，可以说是又好理解又不浪费空间。

vector 常用操作

vector <数据类型> q;//声明一个vector数组

q.push_back(a);//在q数组末尾插入a
//vector 数组是从0开始的

q.size()//返回q数组中数据的多少

q[w]//返回q中下标是w的值，就和普通数组一样

总之，vector 就是一个动态的一维数组

当然 vector 还有很多操作，但是常用的就这几个，其他的请自行bdfs

本题思路

其实就是 dfs 搜索就行了，碰到为 0 的点的时候把当前最长长度更新为 0，如果不是 0 的话就加一，如果在路中间最长长度大于 m 的话就结束当前函数。

之后如果到达叶子结点的话就要 ans++，其他的看代码注释就好了，还可以私信我问我（快中考了，基本不在线了，看到必回）。

这道题目还是很简单的，希望你不要看着题解的代码做，看完思路后自己打一遍。

嗨害嗨，代码来喽

#include<bits/stdc++.h>
#define int long long
#define I using
#define AK namespace
#define IOI std
I AK IOI;
struct zzx{
    vector<int> q;//记录他能到达的点 
    int ch;//类型，看看是0还是1 
}w[200001];
bool vis[200001];//查看是否走过 
int n,m,bo,a,b;
int ans;//记录答案 
void dfs(int x , int sum, bool flag)
//x--当前的位置
//sum--当前的连续的1的长度
//flag--用来判断是否为叶子结点的 
{
    if(sum>m) return ;//如果当前的最大值大于m那直接返回就行了 
    for(int i=0;i<w[x].q.size();i++)
    {
        if(vis[w[x].q[i]]==1) continue;//如果这个点访问过就不能走了 
        flag=1;//就代表他还是有子节点的 
        vis[w[x].q[i]]=1;//标记 
        if(w[ w[x].q[i] ].ch==0) dfs(w[x].q[i],0,0);//如果他的类型是0的话就更新长度为0 
        else
        dfs(w[x].q[i],sum+1,0);//反之就+1 
    }
    if(flag==0)//如果他没有子节点的话就说明他是叶子结点 
    {
        ans++;//答案++ 
        return ;
    }
}

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>bo,
        w[i].ch=bo;//记录权值 
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        w[a].q.push_back(b);            
        w[b].q.push_back(a);//记录a能到b，b能到a 
     } 
     vis[1]=1;
    dfs(1,w[1].ch,0);//搜索 
    cout<<ans;//输出答案 
}