技能大赛卡题少女

遍历图一棵有根节点的树，到达叶子节点不能遇到连续超过m个1，就是一个图的遍历，我TM 卡了这么久，是因为 叶子节点判断错了，阿妈妈咪呀，我发现 dfs 错也不容易查出来呀，以后要 多用printf 输出检查一下了。
邻接表过的

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define ll long long
ll num[N];
int n,m;
struct Node{
int v,u;
}node[N];
int head[N];
int cnt=0;
int a,b;
int ans=0;
bool vis[N];
void init()
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
cnt=0;
}
void add_e(int u,int v)
{
    node[cnt].v=v;
    node[cnt].u=head[u];
    head[u]=cnt++;
}
int dfs(int j,int cc)
{
vis[j]=true;
if(cc<=m)
{
    int f=0;
    for(int i=head[j];i!=-1;i=node[i].u)
    {
        if(!vis[node[i].v])
        {

                    if(num[node[i].v]!=1)
                    {

                        dfs(node[i].v,0);
                    }
                    else{
                        dfs(node[i].v,cc+1);
                    }
f=1;
        }
    }
     if(f==0){
                        //cout<<j<<endl;
                    if(cc<=m)
                    {
                     ans++;
                    }
                }
}
}
int main()
{
   // freopen("1.in","r",stdin);

    cin >> n >> m;
    init();
    for(int i=1;i<=n;i++)
    {
        cin >> num[i];
    }
    for(int i=0;i<n-1;i++)
    {
            cin >> a >> b;
           add_e(b,a);
           add_e(a,b);
    }
    if(num[1]!=1)
    {
     dfs(1,0);
    }
    else
    {
     dfs(1,1);
    }
    cout<<ans;
    return 0;
}

之前写的代码 ,邻接表数组也没乘2倍，cc 在叶子节点也改变了，但是没调出来，(╥╯^╰╥)

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define ll long long
ll num[N];
int n,m;
struct Node{
int v,u;
}node[N];
int head[N];
int cnt=0;
int a,b;
int ans=0;
bool vis[N];
void init()
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
cnt=0;
}
void add_e(int u,int v)
{
    node[cnt].v=v;
    node[cnt].u=head[u];
    head[u]=cnt++;
}
int dfs(int j,int cc)
{
vis[j]=true;
if(cc<=m)
{
    for(int i=head[j];i!=-1;i=node[i].u)
    {
        if(!vis[node[i].v])
        {
             int f=0;
                for(int k=head[node[i].v];k!=-1;k=node[k].u)
                {
                    if(vis[node[k].v]==0)
                    {
                        f=1;
                    }
                }
                if(f==0)
                {
                    int tc=cc;
               // cout<<node[i].v<<" "<<m<<" num "<<num[node[i].v]<<" c "<<cc<<endl;
                    if(num[node[i].v]==1)
                    {
                     tc++;
                    }
                    if(tc<=m)
                    {
                     ans++;
                     vis[node[i].v]=1;
                    }
                }
                else
                {
                    if(num[node[i].v]!=1)
                    {
                        dfs(node[i].v,0);
                    }
                    else{
                        dfs(node[i].v,cc+1);
                    }
                }
        }
    }
}
}
int main()
{
   // freopen("input.txt","r",stdin);
    cin >> n >> m;
    init();
    for(int i=1;i<=n;i++)
    {
        cin >> num[i];
    }
    for(int i=0;i<n-1;i++)
    {
           cin >> a >> b;
           add_e(b,a);
           add_e(a,b);
    }
    if(num[1]!=1)
    {
     dfs(1,0);
    }
    else
    {
     dfs(1,1);
    }
    cout << ans;
    return 0;
}

vector 过的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 100003
vector<int>v[maxn];
int vis[maxn];
bool bv[maxn];
int ans=0;
int n,m;
void dfs(int no,int cn)
{
    bv[no]=1;
    if(vis[no]==1)
    {
        cn++;
    }
    else{
       cn=0;
    }
    if(cn<=m)
    {
        int f=0;
        for(int i=0;i<v[no].size();i++)
        {
            if(bv[v[no][i]]==0)
            {
             dfs(v[no][i],cn);
             f=1;
            }
        }
        if(f==0)
        {
                ans++;
        }

    }
}
int main()
{
 //freopen("input.txt","r",stdin);
 //freopen("output.txt","w",stdout);
    int t;
    int a,b;
    while(cin>>n>>m)
    {
        ans=0;
        memset(bv,0,sizeof(bv));
        t=0;
        for(int i=0;i<n;i++)
        {
            cin>>vis[i+1];
        }
        for(int i=0;i<n-1;i++)
        {
          cin>>a>>b;
          v[a].push_back(b);
          v[b].push_back(a);
        }
        dfs(1,0);
        printf("%d\n",ans);
    }
    return 0;
}

以后水题没做出来，就重新写一遍吧