核心内容摘要
v-viewer组件：一站式图片预览解决方案实现指南
游游的二进制树时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。
获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述游游拿到了一棵树共有n nn个节点每个节点都有一个权值0 00或者1 11。
这样每条路径就代表了一个二进制数。
游游想知道有多少条路径代表的二进制数在[ l , r ] [l,r][l,r]区间范围内请注意路径长度至少为1 11例如节点3 33到节点3 33虽然有一个权值但并不是合法路径输入描述第一行输入三个正整数n , l , r n,l,rn,l,r用空格隔开。
第二行输入一个长度为n nn的01 0101串第i ii个字符代表i ii号节点的权值。
接下来的n − 1 n−1n−1行每行输入两个正整数u uu和v vv代表u uu号节点和v vv号节点有一条边连接。
1 ≤ n ≤ 10 3 1≤n≤10^31≤n≤1031 ≤ u , v ≤ n 1≤u,v≤n1≤u,v≤n1 ≤ l ≤ r ≤ 10 14 1≤l≤r≤10^{14}1≤l≤r≤1014输出描述一个整数代表合法的路径条数。
示例1输入4 4 5 1010 1 2 2 3 3 4输出3说明路径1 − 2 − 3
−2−3代表的二进制数为5 55。
路径3 − 2 − 1
−2−1代表的二进制数为5 55。
路径4 − 3 − 2 − 1
−3−2−1代表的二进制数为5 55。
示例2输入3 1 2 100 1 2 1 3输出6说明任意合法路径均在区间[ l , r ] [l,r][l,r]内。
解题思路本题因n ≤ 1 e 3 n≤1e3n≤1e3采用枚举起点DFS遍历剪枝求解核心是枚举树中每个节点作为路径起点遍历所有以其为起点的简单路径借助父节点避免回走首先将节点的01 0101权值转为数字存储构建邻接表表示树的无向边对每个起点启动D F S DFSDFS参数记录父节点、当前路径的二进制数值、当前节点、路径长度遍历子节点时更新二进制数为v a l ∗ 2 val*2val∗2子节点权值、长度 1 11遍历中若当前值超过r则直接剪枝减少无效计算若值在[ l , r ] [l,r][l,r]且路径长度≥ 2 ≥2≥2满足合法路径要求则计数最终所有合法情况的计数值之和即为答案O ( n 2 ) O(n²)O(n
的时间复杂度完美适配n ≤ 1 e 3 n≤1e3n≤1e3的规模精准统计出符合区间要求的二进制路径数量。
代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpairll,llpii;constll p1e97;constll N1e310;ll q[N];vectorllg[N];ll n,l,r,num;string w;voiddfs(ll fa,ll val,ll u,ll len){if(valr)return;if(valllen