Pagini recente » Cod sursa (job #2054436) | Cod sursa (job #3237233) | Cod sursa (job #2679421) | Cod sursa (job #2166769) | Cod sursa (job #3197244)
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
using namespace std;
namespace __template{
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll getTime(){return chrono::steady_clock::now().time_since_epoch().count();}
mt19937_64 gen(getTime());
ll rndnext(ll l,ll r){
uniform_int_distribution<ll> rng(l,r);
return rng(gen);
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
};
using namespace __template;
const ll NMAX=2e5+5,LGMAX=19,TL=9e8;
const ll MOD=1e9+7,MOD2=2e9+11,base=29;
ll subtreeSize[NMAX],p[NMAX],k,fr[NMAX],sumfr[NMAX],depth[NMAX];
bool blocked[NMAX],visited[NMAX];
vector<ll> edg[NMAX];
ll cnt=0;
void dfs(ll u){
if(depth[u]>=130950) return;
subtreeSize[u]=1;
fr[depth[u]]++;
cnt++;
for(auto it : edg[u]){
if(it!=p[u] && !blocked[it]){
depth[it]=depth[u]+1;
p[it]=u;
dfs(it);
subtreeSize[u]+=subtreeSize[it];
}
}
}
void milka(ll u){
p[u]=0,depth[u]=0,dfs(u);
}
ll findCentroid(ll u){
milka(u);
ll n=subtreeSize[u];
while(1){
bool changed=0;
for(auto it : edg[u]){
if(!blocked[it] && it!=p[u] && subtreeSize[it]*2>n){
u=it;
changed=1;
break;
}
}
if(!changed) break;
}
blocked[u]=1;
return u;
}
ll divide(ll u){
ll v=findCentroid(u);
for(ll i=0;i<=k && (fr[i] || sumfr[i]);i++) sumfr[i]=fr[i]=0;
milka(v);
ll ans=fr[k];
for(ll i=0;i<=k && fr[i];i++) fr[i]=0;
for(auto it : edg[v]){
if(!blocked[it]){
milka(it);
for(ll i=0;i+2<=k && fr[i];i++)
ans+=fr[i]*sumfr[k-i-2];
for(ll i=0;i<=k && fr[i];i++) sumfr[i]+=fr[i],fr[i]=0;
}
}
for(auto it : edg[v]){
if(!blocked[it])
ans+=divide(it);
}
return ans;
}
void tc(){
ll n;
cin>>n>>k;
for(ll i=1;i<n;i++){
ll u,v; cin>>u>>v;
edg[u].push_back(v);
edg[v].push_back(u);
}
cout<<divide(1);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//ll t; cin>>t; while(t--)
tc();
return 0;
}