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

暴力即可：枚举起点dfs。理论上时间复杂度为, 不过由于路径值增长很快（每加一位数，相当于乘以2，大于后即可剪枝），因此单次dfs深度不超过，因此实际时间复杂度为

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    long long n, l, r;
    cin >> n >> l >> r;
    string s;
    cin >> s;
    vector<vector<int>> adj(n + 1, vector<int>());
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    long long ans = 0;

    auto dfs = [&adj, &s, l, r, &ans](auto self, int src, int fa,
    long long num)->void {
        if (num > r || num < 0) return;
        for (auto v : adj[src]) {
            if (v == fa) continue;
            long long cur = (num << 1) | (s[v - 1] - '0');
            if (l <= cur && cur <= r) ans ++;
            self(self, v, src, cur);
        }
    };

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

    cout << ans;
}
// 64 位输出请用 printf("%lld")