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

分析

注意到数据范围不大

点的数量是, 边的数量也是

可以用解决

• 每个点作为根查找一下路径
• 发现满足条件累计答案

算法时间复杂度可以通过

代码实现

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e3 + 10;

int n;
LL l, r;
LL w[N];
vector<int> g[N];
int ans = 0;

void dfs(int u, int fa, LL cur, int cnt) {
    if (cur > r) return;
    if (cnt >= 1 && cur >= l && cur <= r) ans++;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u, (cur << 1ll) + w[v], cnt + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> l >> r;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); ++i) w[i + 1] = s[i] - '0';

    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

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

    cout << ans << '\n';
    return 0;
}