This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 木の重心列挙 O(N)
// 重心を一つ求める O(N) (列挙よりも高速)
// 重心分解する
#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
using Graph = vector< vector<int> >;
const long long int MOD = 1000000007;
// 木の重心を列挙する
// 重心 v → v を根とした時に、 v の子を根とする部分木のサイズが全て N/2 以下である
// DFS をすることで容易に判定可能 O(N)
vector<int> treeCentroid(Graph &G) {
int N = G.size();
vector<int> centroid, val(N);
function<void (int, int)> dfs = [&](int cur, int par) {
bool is_centroid = true;
val[cur] = 1;
for(auto to : G[cur]) {
if(to == par) continue;
dfs(to, cur);
val[cur] += val[to];
if(val[to] > N / 2) is_centroid = false;
}
if(N - val[cur] > N / 2) is_centroid = false;
if(is_centroid) centroid.push_back(cur);
};
dfs(0, -1);
return centroid;
}
// 部分木の重心をひとつ求める (通行できない頂点は dead で管理)
// 子を根としたときの部分木のサイズが N/2 を超えていれば、その子を新たに根として探索
int oneCentroid(Graph &G, int root, vector<bool> &dead) {
// 毎回確保すると遅いので必ず static にしよう
static vector<int> val((int)G.size());
function<void (int, int)> get_size = [&](int cur, int par) {
val[cur] = 1;
for(auto to : G[cur]) {
if(to == par || dead[to]) continue;
get_size(to, cur);
val[cur] += val[to];
}
};
get_size(root, -1);
int N = val[root];
function<int (int, int)> dfs = [&](int cur, int par) {
for(auto to : G[cur]) {
if(to == par || dead[to]) continue;
if(val[to] > N / 2) return dfs(to, cur);
}
return cur;
};
return dfs(root, -1);
}
int calc_pairs(vector<int> &paths, int k) {
sort(paths.begin(), paths.end());
int N = paths.size(), idx = N - 1, ans = 0;
for(int i=0; i<N; i++) {
while(idx >= 0 && paths[i] + paths[idx] > k) idx--;
ans += (idx + 1) - (idx >= i ? 1 : 0);
}
return ans / 2;
}
// 重心分解テンプレート
int centroidDecomposition(Graph &G, int k) {
int N = G.size();
// 切られた場所
vector<bool> dead(N, false);
int ans = 0;
function<void (int)> rec = [&](int root) {
int c = oneCentroid(G, root, dead);
dead[c] = true; // 重心となる頂点で木を分割する
// 重心で切ったときにできる部分木に対して値を求める
for(auto to : G[c]) {
if(dead[to]) continue;
rec(to);
}
// 重心と部分木を使ってマージ
// 下では、長さ k 以下のパスの数を求めている
/*
vector<int> whole_paths;
whole_paths.push_back(0);
for(auto to : G[c]) {
if(dead[to]) continue;
vector<int> paths;
function<void (int, int, int)> enumerate_paths = [&](int cur, int pre, int dist) {
paths.push_back(dist);
for(auto nxt : G[cur]) {
if(nxt == pre || dead[nxt]) continue;
enumerate_paths(nxt, cur, dist + 1);
}
};
enumerate_paths(to, c, 1);
ans -= calc_pairs(paths, k);
ans += calc_pairs(paths, k-1);
whole_paths.insert(whole_paths.end(), paths.begin(), paths.end());
}
ans += calc_pairs(whole_paths, k);
ans -= calc_pairs(whole_paths, k-1);
*/
dead[c] = false; // 再帰なので抜けるときはもとに戻す
};
rec(0);
return ans;
}
int main() {
int N, K; scanf("%d%d", &N, &K);
Graph G(N);
for(int i=0; i<N-1; i++) {
int u, v; scanf("%d%d", &u, &v);
u--; v--;
G[u].push_back(v);
G[v].push_back(u);
}
long long int val = centroidDecomposition(G, K);
// cout << "val: " << val << endl;
long long int mul = ((long long int)K * (K+1) / 2) % MOD;
printf("%lld\n", (val * mul) % MOD);
return 0;
}
#line 1 "graph/graph_021_centroid.cpp"
// 木の重心列挙 O(N)
// 重心を一つ求める O(N) (列挙よりも高速)
// 重心分解する
#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
using Graph = vector< vector<int> >;
const long long int MOD = 1000000007;
// 木の重心を列挙する
// 重心 v → v を根とした時に、 v の子を根とする部分木のサイズが全て N/2 以下である
// DFS をすることで容易に判定可能 O(N)
vector<int> treeCentroid(Graph &G) {
int N = G.size();
vector<int> centroid, val(N);
function<void (int, int)> dfs = [&](int cur, int par) {
bool is_centroid = true;
val[cur] = 1;
for(auto to : G[cur]) {
if(to == par) continue;
dfs(to, cur);
val[cur] += val[to];
if(val[to] > N / 2) is_centroid = false;
}
if(N - val[cur] > N / 2) is_centroid = false;
if(is_centroid) centroid.push_back(cur);
};
dfs(0, -1);
return centroid;
}
// 部分木の重心をひとつ求める (通行できない頂点は dead で管理)
// 子を根としたときの部分木のサイズが N/2 を超えていれば、その子を新たに根として探索
int oneCentroid(Graph &G, int root, vector<bool> &dead) {
// 毎回確保すると遅いので必ず static にしよう
static vector<int> val((int)G.size());
function<void (int, int)> get_size = [&](int cur, int par) {
val[cur] = 1;
for(auto to : G[cur]) {
if(to == par || dead[to]) continue;
get_size(to, cur);
val[cur] += val[to];
}
};
get_size(root, -1);
int N = val[root];
function<int (int, int)> dfs = [&](int cur, int par) {
for(auto to : G[cur]) {
if(to == par || dead[to]) continue;
if(val[to] > N / 2) return dfs(to, cur);
}
return cur;
};
return dfs(root, -1);
}
int calc_pairs(vector<int> &paths, int k) {
sort(paths.begin(), paths.end());
int N = paths.size(), idx = N - 1, ans = 0;
for(int i=0; i<N; i++) {
while(idx >= 0 && paths[i] + paths[idx] > k) idx--;
ans += (idx + 1) - (idx >= i ? 1 : 0);
}
return ans / 2;
}
// 重心分解テンプレート
int centroidDecomposition(Graph &G, int k) {
int N = G.size();
// 切られた場所
vector<bool> dead(N, false);
int ans = 0;
function<void (int)> rec = [&](int root) {
int c = oneCentroid(G, root, dead);
dead[c] = true; // 重心となる頂点で木を分割する
// 重心で切ったときにできる部分木に対して値を求める
for(auto to : G[c]) {
if(dead[to]) continue;
rec(to);
}
// 重心と部分木を使ってマージ
// 下では、長さ k 以下のパスの数を求めている
/*
vector<int> whole_paths;
whole_paths.push_back(0);
for(auto to : G[c]) {
if(dead[to]) continue;
vector<int> paths;
function<void (int, int, int)> enumerate_paths = [&](int cur, int pre, int dist) {
paths.push_back(dist);
for(auto nxt : G[cur]) {
if(nxt == pre || dead[nxt]) continue;
enumerate_paths(nxt, cur, dist + 1);
}
};
enumerate_paths(to, c, 1);
ans -= calc_pairs(paths, k);
ans += calc_pairs(paths, k-1);
whole_paths.insert(whole_paths.end(), paths.begin(), paths.end());
}
ans += calc_pairs(whole_paths, k);
ans -= calc_pairs(whole_paths, k-1);
*/
dead[c] = false; // 再帰なので抜けるときはもとに戻す
};
rec(0);
return ans;
}
int main() {
int N, K; scanf("%d%d", &N, &K);
Graph G(N);
for(int i=0; i<N-1; i++) {
int u, v; scanf("%d%d", &u, &v);
u--; v--;
G[u].push_back(v);
G[v].push_back(u);
}
long long int val = centroidDecomposition(G, K);
// cout << "val: " << val << endl;
long long int mul = ((long long int)K * (K+1) / 2) % MOD;
printf("%lld\n", (val * mul) % MOD);
return 0;
}