建设银行企业网银网站过期,嵌入式软件开发工具的发展趋势是什么,建设网站设计的公司,优享购物官方网站题目描述
游游拿到了一棵树#xff0c;共有nnn个节点#xff0c;每个节点都有一个权值#xff1a;0或者1。这样#xff0c;每条路径就代表了一个二进制数。 游游想知道#xff0c;有多少条路径代表的二进制数在[l,r][l,r][l,r]区间范围内#xff1f; #xff08;请注意…题目描述
游游拿到了一棵树共有nnn个节点每个节点都有一个权值0或者1。这样每条路径就代表了一个二进制数。 游游想知道有多少条路径代表的二进制数在[l,r][l,r][l,r]区间范围内 请注意路径长度至少为1例如节点3到节点3虽然有一个权值但并不是合法路径
输入描述:
第一行输入三个正整数n,l,r用空格隔开。
第二行输入一个长度为n的01串第i个字符代表i号节点的权值。
接下来的n−1行每行输入两个正整数u和v代表u号节点和v号节点有一条边连接。
1≤n≤103
1≤u,v≤n
1≤l≤r≤1014
输出描述: 一个整数代表合法的路径条数。
示例1
输入
4 4 5
1010
1 2
2 3
3 4
输出
3
说明 路径1-2-3代表的二进制数为5。
路径3-2-1代表的二进制数为5。
路径4-3-2-1代表的二进制数为5。
示例2
输入
3 1 2
100
1 2
1 3
输出
6
说明
任意合法路径均在区间[l,r]内。
代码实现
#includebits/stdc.h
using namespace std;
const int N2e510;
vectorlong longh[N];
string s;
long long n,l,r,ans;void dfs(int u,int fa,long long mid){midmid*2s[u-1]-0; //每次加上该点位的权值 if(midr)return; //如果大于r则该路径不合法退出递归 if(famidl)ans; //fa代表节点数 fa大于1代表最少2个节点 for(int v:h[u]){ //if(fav)continue;//不合法了节点不会回头 dfs(v,u,mid); //遍历以这一个节点的第一个值为节点的路径 }
}int main(){cinnlrs;for(int i1;in;i){int x,y;cinxy;h[x].push_back(y); //可以存储以一个数为起点能达到的所有点 h[y].push_back(x);}for(int i1;in;i)dfs(i,0,0); //从第一个点开始查询搜索所有以该点为起点的路径 coutansendl;return 0;
}
