题解 | 游游的二进制树

本题中，很重要的剪枝思想就是如果此时的值已经大于r了，那么接下来再深搜就已经没有必要了

此外就是关于下一个边的值的计算方法

nv = (val << 1) | w[v];

是二进制的运算方式，意思是对上一个的val乘2后加上当前的值的大小

#include <bits/stdc++.h>
using namespace std;
#define sc second
#define fr first
#define int long long
#define itn long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define endl '\n'
#define enld '\n'
#define all(a) a.begin(), a.end()
#define ui unordered_map<int, int>
#define pi acos(-1)
int n;
int L, R;
string s;
vvi g;
vi w;
int ans = 0;
void dfs(int start, int u, int fa, int val)
{
    if (u != start && val >= L && val <= R)
        ans++;//如果结果符合的话就对ans+1

    for (int v : g[u])
    {
        if (v == fa)
            continue;//避免回溯搜索
        int nv = (val << 1) | w[v];
        if (nv > R)
            continue;//剪枝
        dfs(start, v, u, nv);
    }
}

void _()
{
    cin >> n >> L >> R;
    cin >> s;
    w.assign(n + 1, 0);
    for (int i = 1; i <= n; i++)
        w[i] = s[i - 1] - '0';
    g.assign(n + 1, {});
    ans = 0;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    //以上均为初始化
    for (int start = 1; start <= n; start++)//时间复杂度允许，直接暴力搜索就行
    {
        for (int v : g[start])
        {
            int val = ((int)w[start] << 1) | w[v];
            if (val > R)
                continue;
            dfs(start, v, start, val);
        }
    }

    cout << ans << endl;//觉得不错的话记得点个赞哦awa
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int awa = 1;
    // cin >> awa;
    while (awa--)
    {
        _();
    }
    return 0;
}