遍历图一棵有根节点的树，到达叶子节点不能遇到连续超过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;
}
以后水题没做出来，就重新写一遍吧
