題目描述

游游拿到了一棵樹，共有nnn個節(jié)點，每個節(jié)點都有一個權值：0或者1。這樣，每條路徑就代表了一個二進制數(shù)。
游游想知道，有多少條路徑代表的二進制數(shù)在[l,r][l,r][l,r]區(qū)間范圍內(nèi)？
（請注意：路徑長度至少為1，例如，節(jié)點3到節(jié)點3雖然有一個權值，但并不是合法路徑！）

輸入描述:

第一行輸入三個正整數(shù)n,l,r用空格隔開。
第二行輸入一個長度為n的01串，第i個字符代表i號節(jié)點的權值。
接下來的n?1行，每行輸入兩個正整數(shù)u和v，代表u號節(jié)點和v號節(jié)點有一條邊連接。
1≤n≤103
1≤u,v≤n
1≤l≤r≤1014

輸出描述:

一個整數(shù)，代表合法的路徑條數(shù)。

示例1

輸入

4 4 5
1010
1 2
2 3
3 4

輸出

3

說明

路徑1-2-3代表的二進制數(shù)為5。

路徑3-2-1代表的二進制數(shù)為5。

路徑4-3-2-1代表的二進制數(shù)為5。

示例2

輸入

3 1 2
100
1 2
1 3

輸出

6

說明

任意合法路徑均在區(qū)間[l,r]內(nèi)。

代碼實現(xiàn)

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<long long>h[N];
string s;
long long n,l,r,ans;void dfs(int u,int fa,long long mid){mid=mid*2+s[u-1]-'0';  //每次加上該點位的權值 if(mid>r)return;  //如果大于r則該路徑不合法，退出遞歸 if(fa&&mid>=l)ans++;  //fa代表節(jié)點數(shù) fa大于1代表最少2個節(jié)點 for(int v:h[u]){     //if(fa==v)continue;//不合法了，節(jié)點不會回頭 dfs(v,u,mid);     //遍歷以這一個節(jié)點的第一個值為節(jié)點的路徑 }
}int main(){cin>>n>>l>>r>>s;for(int i=1;i<n;i++){int x,y;cin>>x>>y;h[x].push_back(y);  //可以存儲以一個數(shù)為起點，能達到的所有點 h[y].push_back(x);}for(int i=1;i<=n;i++)dfs(i,0,0);     //從第一個點開始查詢，搜索所有以該點為起點的路徑 cout<<ans<<endl;return 0;
}