题解 | #游游的二进制树#

枚举起点 + 带剪枝的 DFS

鉴于 较小，最直接且稳健的算法是：枚举树上的每一个节点作为路径起点，通过深度优先搜索（DFS）向外延伸，寻找所有合法的终点。

全源遍历 (All-Source Traversal) + 状态传递

由于二进制数的计算依赖于节点的访问顺序（），从某个起点出发向叶子方向延伸时，当前数值的计算天然契合 DFS 的递归结构。

为什么不使用高级树算法？

• 点分治 (Centroid Decomposition)：通常用于处理大规模树路径问题（）。虽然可行，但在 的情况下，其实现的复杂度和常数开销相比 的暴力搜索带来的收益微乎其微，反而增加了代码出错的风险。
• 树形 DP：由于路径的值与方向强相关（高位在前），且合并两条路径（）时需要处理位移和拼接，状态极其复杂，不易转移。

因此，枚举起点 + DFS 是当前约束下的最优解。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll l, r;
    cin >> n >> l >> r;

    string w;
    cin >> w;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    ll ans = 0;

    auto dfs = [&](auto&& self, int u, int p, ll cur_val) -> void {
        for (int v : adj[u]) {
            if (v == p)
                continue;
            ll next_val = cur_val * 2LL + (ll)w[v - 1] - '0';
            if (next_val > r)
                continue;
            if (next_val >= l)
                ans++;
            self(self, v, u, next_val);
        }
    };

    for (int i = 1; i <= n; i++) {
        dfs(dfs, i, -1, w[i - 1] - '0');
    }

    cout << ans << endl;
}