# Help on a centroid decomposition problem

## 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

## My Work

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+12;
int n,k1,k2;
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;
x+1,lx,mid);
sums[x]=sums[2
x+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,2
x+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;
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){
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;
else ans+=st.sum(max(0,k1-depth),k2-depth,0,0,n);
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;
if(isremoved[child])continue;
dfs(child,centroid,1,false);
dfs(child,centroid,1,true);
}
st.sums.assign(st.size*2,0LL);
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--;

}
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;
``````

}

The solutions at Solution - Fixed-Length Paths II (CSES) are one or two logs faster than yours.