d294529e.cpp

/**
 * @brief
 * 在树上取两个点 a, b，dis(a, b) 为偶数，求第三个点 c 到 a, b 距离的较大值
 * max{dis(a, c), dis(b, c)} == dis(c, T) + dis(a, b) / 2
 * 其中 T 为 a, b 中点
 */

#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
                           << (#x) << ": " << x << std::endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    static char c;
    static bool neg;
    x = 0, c = getchar(), neg = false;
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 2 * 4000 + 5;

typedef unsigned short u16;

vector<int> G[N];

inline void addE(int u, int v)
{
    G[u].emplace_back(v);
    G[v].emplace_back(u);
}

u16 f[N][N];

int n, k;

void dfs(int u, int fa, int dep, u16 *f)
{
    if (u <= n)
    {
        ++f[dep];
    }
    for (const auto &v : G[u])
    {
        if (v != fa)
        {
            dfs(v, u, dep + 1, f);
        }
    }
}

ll ans = 0;
int a[N];

void calc(int u, int fa, int dep)
{
    if (dep > 2 * k)
    {
        return;
    }
    if (dep)
    {
        ans += f[a[dep / 2]][2 * k - dep / 2] - 2;
    }
    for (const auto &mid : G[u])
    {
        int v;
        if ((v = G[mid].front()) == u)
        {
            v = G[mid].back();
        }
        if (v != fa)
        {
            a[dep + 1] = mid;
            a[dep + 2] = v;
            calc(v, u, dep + 2);
        }
    }
}

int main()
{
    read(n), read(k);
    for (int i = 1, u, v, mid = n + 1; i < n; ++i, ++mid)
    {
        read(u), read(v);
        addE(u, mid);
        addE(mid, v);
    }
    for (int i = 1; i <= 2 * n - 1; ++i)
    {
        dfs(i, 0, 0, f[i]);
    }
    for (int i = 1; i <= 2 * n - 1; ++i)
    {
        for (int j = 1; j <= 2 * n - 1; ++j)
        {
            f[i][j] += f[i][j - 1];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        calc(i, 0, 0);
    }
    printf("%lld\n", ans);
}