这道题虽然代码量不大，但考察的基础知识点非常扎实，是典型的图论搜索 + 基础数论结合的题目。

以下是这道题的 5 个核心考点总结：

1. 图的存储（邻接表）

  • 考点：如何用 C++ 的 STL 存储一棵树（无向图）。
  • 要点：使用 vector<int> g[N]。
  • 注意区分 vector<int> g(n)（定义1个长度为n的vector）和 vector<int> g[N]（定义N个vector的数组）。
  • 无向图需要存双向边 (u->v 和 v->u)。

2. 深度优先搜索 (DFS) 的状态传递

  • 考点：如何在递归过程中携带“当前路径的状态”。
  • 参数设计：
  • u：当前在哪。
  • fa：防回头（防止死循环，树形DFS的标准操作）。
  • val：当前路径累积的数值。
  • len：当前路径的长度（用于判断是否合法）。

3. 二进制转十进制（秦九韶算法思想）

  • 考点：如何在遍历过程中实时计算二进制数值，而不是存成字符串最后再转。
  • 公式：new_val = old_val * 2 + current_bit。
  • 这也是所有“高位在前的进制转换”的通用公式。
  • 也可以写成位运算形式：new_val = (old_val << 1) | current_bit。

4. 搜索剪枝 (Pruning) —— 最关键的优化

  • 考点：如何保证程序不超时。
  • 逻辑：题目中 ，如果暴力搜索所有路径，深度可能很深。
  • 剪枝条件：if (val > r) return;
  • 因为二进制数增长极快（指数级），只要当前值超过了 （ 大约是 ），再往下走数值只会更大，不可能变小回到 区间，所以必须立刻停止。这大大减少了搜索量。

5. 数据范围与类型

  • 考点：对数据溢出的敏感度。
  • 陷阱： 最大为 。
  • int 最大约为 。
  • 必须使用 long long（最大约 ），否则只能过一部分测试用例。

💡 举一反三（下一步建议）

既然你已经掌握了这题，可以尝试思考这几个变种，看看思路有什么不同：

  1. 如果权值是在“边”上而不是“点”上，代码需要怎么改？
  • (提示：dfs 参数里的权值要在遍历 v 的时候加上 edge_weight)
  1. 如果问的是“所有路径权值之和”，应该怎么做？
  2. 如果 很大（比如 ），这种 的枚举起点的做法会超时，该怎么优化？
  • (这通常需要“点分治”或者“Trie树”等高级技巧，是进阶题)

你想试试“权值在边上”这种小改动吗？

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n;
long long l,r;
string w;
int p[N];
vector<int>g[N];
long long num=0;
void dfs(int fa,long long val,int u,int len){
	if(val>r) return;
	if(val>=l && len>=2){
		num++;
	}
	for(int v:g[u]){
		if(v==fa) continue;
		dfs(u,val*2+p[v],v,len+1);
	}
}
int main(){
	cin>>n>>l>>r>>w;
	for(int i=1;i<=n;i++) p[i]=w[i-1]-'0';
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		dfs(0,p[i],i,1);
	}
	cout<<num;
}