Checklist
Make sure to read all of How to ask for help on a problem before asking for help.
Fixed-length-paths : link :CSES - Fixed-Length Paths II
I tried range queries( segment tree )to calculate the number of paths but it gives TLE and even the solution using BIT ,even though faster,still gives TLE
My Work
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+12;
int n,k1,k2;
vectoradj[N];
int sz[N];
bool isremoved[N];
long long ans;
//segment tree data-structure
struct segtree{
int size;
vectorsums;
void build(int n){
size=1;
while(size<n)size*=2;
sums.assign(2size,0LL);
}
void add(int pos,int x,int lx,int rx){
if(rx-lx==1){
sums[x]++;
return;
}
int mid=lx-(lx-rx)/2;
if(pos<mid)add(pos,2x+1,lx,mid);
else add(pos,2x+2,mid,rx);
sums[x]=sums[2x+1]+sums[2x+2];
}
long long sum(int l,int r,int x,int lx,int rx){
if(rx<=l || lx>=r)return 0LL;
if(rx<=r && lx>=l)return sums[x];
int mid=lx-(lx-rx)/2;
return sum(l,r,2x+1,lx,mid)+sum(l,r,2*x+2,mid,rx);
}
};
segtree st;
//calculating subtree sizes of each centroid
int subtreesize(int node,int parent){
sz[node]=1;
for(int child:adj[node]){
if(isremoved[child]||child==parent)continue;
sz[node]+=subtreesize(child,node);
}
return sz[node];
}
//find the centroid
int getcentroid(int node,int parent,int treesize){
for(int child:adj[node]){
if(isremoved[child]||child==parent)continue;
if(treesize<sz[child]*2){
return getcentroid(child,node,treesize);
}
}
return node;
}
//code to calculate number of paths ( modified dfs)
void dfs(int node,int parent,int depth,bool usingcentroid){
if(depth>k2)return;
if(usingcentroid)st.add(depth,0,0,n);
else ans+=st.sum(max(0,k1-depth),k2-depth,0,0,n);
for(int child:adj[parent]){
if(isremoved[child]||child==parent)continue;
dfs(child,node,depth+1,usingcentroid);
}
}
//building the centroid decomposition
void build(int node){
int centroid=getcentroid(node,node,subtreesize(node,node));
isremoved[centroid]=true;
for(int child:adj[centroid]){
if(isremoved[child])continue;
dfs(child,centroid,1,false);
dfs(child,centroid,1,true);
}
st.sums.assign(st.size*2,0LL);
for(int child:adj[centroid]){
if(isremoved[child])continue;
build(child);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k1>>k2;
int u,v;
for(int i=0;i<n-1;i++){
cin>>u;
cin>>v;
u--;v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
ans=0;
memset(isremoved,false,sizeof(isremoved));
memset(sz,0,sizeof(sz));
st.build(n);
st.add(0,0,0,n);
build(0);
ans/=2;
cout<<ans;
return 0;
}