Cod sursa(job #3197244)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 26 ianuarie 2024 11:13:18
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.11 kb
#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;
}