codeforces 850C dfs

我用邻接表储存的，dfs遍历了这棵树，求得解。

AC代码：

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxv=1e5+10;
const int maxe=1e5+10;
const int inf=0x3f3f3f3f;

int head[2*maxv];
struct EDGE
{
    int d,next;
    EDGE():next(-1){};
}e[maxe*2];
int which=1;
bool cat[maxv];

void add(int s,int d)
{
    e[which].d=d;
    e[which].next=head[s];
    head[s]=which++;
}
int ans=0;
int n,m;//n is the number of vertexes and m is the number of maximum number he can hold.

//我并不是要找到某一个状态，而是要dfs找出某个值.
void dfs(int x,int father,int catnum)
{

    // sum the consecutive cat number.
    if(cat[x]) catnum++;
    else catnum=0;
    if(catnum>m) return;

    //当前是x节点
    bool xisleaf=1;
    for(int i=head[x];i!=-1;i=e[i].next)
    {
        int d=e[i].d;

        if(d==father) continue;

        xisleaf=0;
        dfs(d,x,catnum);
    }

    if(xisleaf) ans++;

    return;
}

int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(e,0,sizeof(e));
        memset(cat,0,sizeof(cat));
        memset(head,-1,sizeof(head));
        which=1;
        ans=0;

        for(int i=1;i<=n;i++) scanf("%d",&cat[i]);

        for(int i=1;i<=n-1;i++)
        {
            int s,d;
            scanf("%d%d",&s,&d);
            add(s,d);
            add(d,s);
        }

        dfs(1,-1,0);

        printf("%d\n",ans);
    }
}

很惭愧我认为一直到现在我还是不熟悉dfs。

这里给自己一点提醒那就是，考虑当前状态不要考虑下一个状态，下一个状态是下一个dfs的事而不是你这个dfs的事。