题解：P11108 [ROI 2023] 蜗牛与富士山 (Day 2)

**树形dp板子题**
## 分析
 考虑每个节点：如果不是叶子节点，要么往左边走，要么往右边走，所以这个节点的答案就是他的两个子节点的答案之和。如果是叶子节点，那么他就只能到他自己，所以答案为1。

综上所述，我们对于每个非叶子节点，可以递归求出他的两个子节点的答案（这里`dp[i]`表示编号为 $i$ 的节点的答案），并将其累加得到这个节点的答案；对于叶子节点，直接返回1即可。

考虑到还有转弯次数的限制，我们在递归函数中加入两个参数（这里用`dep`和`bl`），分别用来记录到这个节点转了几次弯（因为树上路径是唯一的，所以到这个节点的转弯次数也是固定的），以及上一个节点是往哪边走（这里 $1$ 代表往右， $0$ 代表往左），向子节点递归的时候简单判一下做出处理即可（是否增加转弯次数，转弯次数是否超过限制等）

每次询问直接 $O(1)$ 输出答案即可，总时间复杂度 $O(n+q)$

## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,q,k,h,u,x,y,dp[200005];
struct node{
	int l,r;//l即当前节点的左孩子，r即当前节点的右孩子
}shu[200005];
int dfs(int ind,int dep,bool bl){
	if(dep>k){//如果转弯次数超过限制，直接返回
		dp[ind]=0;
		return 0;
	}
	if(shu[ind].l==0){//如果当前节点为叶子节点，直接返回1
		dp[ind]=1;
		return 1;
	}
	if(bl){//判断是否转弯，并做出不同处理
		dp[ind]+=dfs(shu[ind].l,dep+1,!bl);//累加两边答案
		dp[ind]+=dfs(shu[ind].r,dep,bl);
	}
	else{
		dp[ind]+=dfs(shu[ind].l,dep,bl);
		dp[ind]+=dfs(shu[ind].r,dep+1,!bl);
	}
	return dp[ind];//返回当前节点答案
}
int main(){
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++){
		cin>>h;
		if(h==2){
			cin>>x>>y;
			shu[i].l=x;
			shu[i].r=y;
		}
	}
	dp[1]+=dfs(shu[1].l,0,0);
	dp[1]+=dfs(shu[1].r,0,1);
	while(q--){
		cin>>u;
		cout<<dp[u]<<endl;//每次询问直接输出答案
	}
    return 0;
}
```

正在渲染内容...