dfs理解
深搜的时机
- 在扩展当前节点的邻边之前，即for当前节点的儿子节点之前，刚进入当前这个节点。
- for完当前节点的所有儿子节点之后，要离开当前节点了。
- 开始for当前节点的扩展邻边时，即刚从当前节点出去。此时可以从父节点向儿子节点传一些信息。
- 遍历完当前儿子节点的情况，回到当前节点。此时可以计算儿子节点的个数等值。
注意：for内的循环语句是在要在当前节点的函数空间内执行多次的！
所以一定要注意两点：
- 是要由父节点算子节点，即父节点信息维护子节点信息。-----> 自顶向下
- 还是由子节点算父节点，即自底向上。
经典父节点向子节点传递信息的例题
4946. 叶子节点 - AcWing题库
给定一棵 个节点的树，节点编号 。
号节点为树的根节点。
每个节点要么是黑色的，要么是白色的。
对于一个叶子节点，如果从该节点到根节点的路径（包括两端节点）中有超过 个黑色节点连续的排列在一起，则称该节点为无效叶子节点。
有效叶子节点数量 = 总叶子节点数量 - 无效叶子节点数量
请你统计，给定树中有效叶子节点的数量。
输入格式
第一行包含两个整数 。
第二行包含 个整数 ，其中 表示第 个节点的颜色， 表示黑色， 表示白色。
接下来 行，每行包含两个整数 ，表示节点 和节点 之间存在一条无向边。
保证输入给定的是一棵树。
输出格式
一个整数，表示给定树中有效叶子节点的数量。
数据范围
前 个测试点满足 。
所有测试点满足 ，，，，。
输入样例1：
4 1
1 1 0 0
1 2
1 3
1 4
输出样例1：
2
输入样例2：
7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
输出样例2：
2
#include <bits/stdc++.h>
using namespace std;
const int N = 100010,M = 2*N;
int h[N],e[M],ne[M],w[N],idx;
int n,m;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u,int fa,int cnt,bool valid)
{
// 扩展当前点的邻边之前，先更新当前节点，即相当于是从父节点向子节点传递信息
if (w[u]) cnt++;
else cnt=0;
if (cnt>m) valid=false;
int son=0; // 记录当前节点的儿子节点个数，只有son==0时，才是叶子结点
int res=0; // 记录当前节点所在子树符合的叶子结点个数
// 开始扩展当前节点的邻边
for (int i=h[u];~i;i=ne[i])
{
int j =e[i];
if (j==fa) continue;
son++; // 这时候更新当前节点的儿子节点个数
res+=dfs(j,u,cnt,valid);
}
// 当前节点的所有扩展邻边已经遍历完毕，回到了当前节点。
// 这时候判断一下当前节点是否没有儿子节点（即是叶子结点）并且符合要求
if (!son && valid) res++;
return res;
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
for (int i=0;i<n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
int ans = dfs(1,-1,0,1);
printf("%d\n",ans);
return 0;
}