题解 | 游游的二进制树

注意到，本题用dfs解决，但是要防止溢出，所以写法很关键（不然应该会18/20，别问我咋知道的）代码如下：

#include<bits/stdc++.h>
#include <functional>
#include <vector>
using namespace std;
#define int long long
void solve(){
    int n,l,r;cin>>n>>l>>r;
    string s;cin>>s;
    vector<vector<int>> e(n+1);
    for(int i=1;i<=n-1;i++){
        int a,b;cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    int ans=0;
    auto dfs=[&](auto &&self,int u,int pr,int cur,int cnt)->void{
        if(cur>r) return;
        if(cnt>=1&&cur>=l&&cur<=r) ans++;
        for(auto i:e[u]){
            if(i==pr) continue;
            self(self,i,u,cur*2+s[i-1]-'0',cnt+1);
        }
    };
    for(int i=1;i<=n;i++){
        dfs(dfs,i,0,s[i-1]-'0',0);
    }
    cout<<ans;
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}