游游的二进制树【牛客tracker 每日一题】

游游的二进制树

时间限制：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≤103
1 ≤ u , v ≤ n 1≤u,v≤n1≤u,v≤n
1 ≤ 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 1-2-31−2−3代表的二进制数为5 55。
路径3 − 2 − 1 3-2-13−2−1代表的二进制数为5 55。
路径4 − 3 − 2 − 1 4-3-2-14−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*2+val∗2+子节点权值、长度+ 1 +1+1；遍历中若当前值超过r则直接剪枝（减少无效计算），若值在[ l , r ] [l,r][l,r]且路径长度≥ 2 ≥2≥2（满足合法路径要求）则计数；最终所有合法情况的计数值之和即为答案，O ( n 2 ) O(n²)O(n2)的时间复杂度完美适配n ≤ 1 e 3 n≤1e3n≤1e3的规模，精准统计出符合区间要求的二进制路径数量。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e3+10;ll q[N];vector<ll>g[N];ll n,l,r,num;string w;voiddfs(ll fa,ll val,ll u,ll len){if(val>r)return;if(val>=l&&len>=2)num++;for(ll v:g[u]){if(v==fa)continue;dfs(u,val*2+q[v],v,len+1);}}intmain(){cin>>n>>l>>r>>w;for(ll i=1;i<=n;i++)q[i]=w[i-1]-'0';for(ll i=1;i<=n-1;i++){ll u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}for(ll i=1;i<=n;i++)dfs(0,q[i],i,1);cout<<num<<endl;return0;}