結果

問題 No.1075 木の上の山
コンテスト
ユーザー ats5515
提出日時 2020-06-05 22:00:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,341 bytes
コンパイル時間 1,853 ms
コンパイル使用メモリ 176,288 KB
実行使用メモリ 27,136 KB
最終ジャッジ日時 2024-12-17 14:50:35
合計ジャッジ時間 6,228 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int MOD = 1000000007;
vector<vector<int> > g;
vector<vector<vector<int> > > dp;
vector<vector<int> > prod;
void extgcd(int a, int b, int& x, int& y) {
	if (b != 0) {
		extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1;
		y = 0;
	}
}

int mod_inverse(int a, int p) {
	int x, y;
	extgcd(a, p, x, y);
	return (p + x % p) % p;
}

void add(int& a, const int& b) {
	a += b;
	if (a >= MOD) a -= MOD;
}
int N, K;
vector<int> P;
void dfs1(int a, int p) {
	for (int i = 0; i < g[a].size(); i++) {
		if (g[a][i] != p) {
			dfs1(g[a][i], a);
			for (int k = 0; k < K; k++) {
				dp[a][i][k] = prod[g[a][i]][k];
			}
			for (int k = 1; k < K; k++) {
				add(dp[a][i][k], dp[a][i][k - 1]);
			}
			for (int k = 0; k < K; k++) {
				prod[a][k] = (prod[a][k] * dp[a][i][k]) % MOD;
			}
		}
	}
}

void dfs2(int a, int p, int x) {
	for (int i = 0; i < g[a].size(); i++) {
		if (g[a][i] != p) {
			dfs2(g[a][i], a, i);
		} else {
			P[a] = i;
			for (int k = 0; k < K; k++) {
				dp[a][i][k] = prod[p][k] * mod_inverse(dp[p][x][k], MOD) % MOD;
			}
			for (int k = 1; k < K; k++) {
				add(dp[a][i][k], dp[a][i][k - 1]);
			}
			for (int k = 0; k < K; k++) {
				prod[a][k] = (prod[a][k] * dp[a][i][k]) % MOD;
			}
		}
	}
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N >> K;
	P.resize(N, -1);
	g.resize(N);
	dp.resize(N);
	prod.resize(N, vector<int>(K, 1));
	int res = 0;
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 0; i < N; i++) {
		dp[i].resize(g[i].size(), vector<int>(K, 0));
	}
	dfs1(0, -1);
	dfs2(0, -1, -1);

	// for (int i = 0; i < N; i++) {
	// 	for (int j = 0; j < g[i].size(); j++) {
	// 		cerr << i << "->" << g[i][j] << endl;
	// 		for (int k = 0; k < K; k++) {
	// 			cerr << dp[i][j][k] << " ";
	// 		}
	// 		cerr << endl;
	// 	}
	// }
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < g[i].size(); j++) {
			if (j != P[i]) {
				int b = g[i][j];
				assert(g[b][P[b]] == i);
				for (int k = 1; k < K; k++) {
					add(res, ((dp[i][j][k] - dp[i][j][k - 1]) * dp[b][P[b]][k - 1]) % MOD);
				}
			}
		}
	}
	for (int k = 0; k < K; k++) {
		add(res, prod[0][k]);
	}

	add(res, MOD);
	add(res, MOD);
	add(res, MOD);

	cout << res << endl;
}
0