#include <stdio.h>#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <time.h>#include <queue>template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c - '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;typedef unsigned long long ll;const int N = 100005;struct Edge{int from, to, nex;}edge[N << 1];int head[N], edgenum;void add(int u, int v){ Edge E = { u, v, head[u] }; edge[edgenum] = E; head[u] = edgenum++; }int size[N], parent[N];void dfs_init(int u, int fa){size[u] = 1; parent[u] = fa;for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].to; if (v == fa)continue;dfs_init(v, u);size[u] += size[v];}}int n, k, maxdep;int dp[N], num[N]; int root;bool vis[N];int siz;int G[N], top;void getroot(int u, int fa, int deep){dp[u] = 0; num[u] = 1;maxdep = max(maxdep, deep);for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].to; if (v == fa || vis[v])continue;getroot(v, u, deep + 1);num[u] += num[v];dp[u] = max(dp[u], num[v]);}dp[u] = max(dp[u], siz - num[u]);if (dp[u] < dp[root])root = u;}ll ans, sum[2][N], w[N];int dep[N];ll Siz(int u, int v){if (v == parent[u])return size[u];else return n - size[v] ;}void dfs(int u, int fa, int deep){dep[u] = deep; maxdep = max(maxdep, deep);w[u] = Siz(u, fa) * (Siz(u, fa) - 1);num[u] = 1;G[top++] = u;for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].to; if (v == fa)continue;w[u] -= Siz(v, u) * Siz(v, u);if (vis[v])continue;dfs(v, u, deep + 1);num[u] += num[v];}w[u] += Siz(u, fa);}void work(int u){siz = num[u];root = maxdep = 0;getroot(u, u, 0);if (maxdep * 2 < k)return;int old = 1, cur = 0;fill(sum[cur], sum[cur] + maxdep + 10, 0);sum[cur][0] = 1;ll all = n, fang = 0;for (int i = head[root]; ~i; i = edge[i].nex){int v = edge[i].to;fang += Siz(v, root) * Siz(v, root);}for (int i = head[root], j; ~i; i = edge[i].nex){int V = edge[i].to; if (vis[V])continue;top = 0;dfs(V, root, 1);swap(old, cur);fill(sum[cur], sum[cur] + maxdep + 10, 0);for (j = 0; j < top; j++) sum[cur][dep[G[j]]] += w[G[j]];for (j = 0; j <= maxdep; j++){if (k-j <= maxdep)ans += sum[cur][j] * sum[old][max(0, k-j)];}for (j = maxdep-1; j >= 0; j--) sum[cur][j] += sum[cur][j + 1];if (k <= maxdep)ans += sum[cur][k] * (all - Siz(V, root) - 1 + (all - Siz(V, root)) * (all - Siz(V, root) - 1) - (fang - Siz(V, root)*Siz(V, root)));for (j = maxdep; j >= 0; j--)sum[cur][j] += sum[old][j];}vis[root] = true;for (int i = head[root]; ~i; i = edge[i].nex)if (false == vis[edge[i].to]) work(edge[i].to);}int main(){dp[0] = N;int T; rd(T);while (T--){rd(n); rd(k);memset(head, -1, sizeof head); edgenum = 0;for (int i = 1, u, v; i < n; i++){rd(u); rd(v); add(u, v); add(v, u);}dfs_init(1, 1);ans = 0;num[1] = n;memset(vis, 0, sizeof vis);work(1);ll all = (ll)n*(n + 1) / 2;cout << (all * all - ans) << endl;}return 0;}
