結果

問題 No.1075 木の上の山
ユーザー ats5515ats5515
提出日時 2020-06-05 22:14:35
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 369 ms / 2,000 ms
コード長 2,426 bytes
コンパイル時間 2,015 ms
コンパイル使用メモリ 175,232 KB
実行使用メモリ 27,136 KB
最終ジャッジ日時 2024-05-09 21:41:14
合計ジャッジ時間 6,802 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 5 ms
5,376 KB
testcase_09 AC 6 ms
5,376 KB
testcase_10 AC 6 ms
5,376 KB
testcase_11 AC 5 ms
5,376 KB
testcase_12 AC 6 ms
5,376 KB
testcase_13 AC 7 ms
5,376 KB
testcase_14 AC 7 ms
5,376 KB
testcase_15 AC 8 ms
5,376 KB
testcase_16 AC 7 ms
5,376 KB
testcase_17 AC 365 ms
27,136 KB
testcase_18 AC 155 ms
27,008 KB
testcase_19 AC 369 ms
27,136 KB
testcase_20 AC 158 ms
27,008 KB
testcase_21 AC 260 ms
27,008 KB
testcase_22 AC 257 ms
27,008 KB
testcase_23 AC 260 ms
27,008 KB
testcase_24 AC 262 ms
27,008 KB
testcase_25 AC 258 ms
27,008 KB
testcase_26 AC 157 ms
27,008 KB
testcase_27 AC 210 ms
27,136 KB
testcase_28 AC 313 ms
27,136 KB
testcase_29 AC 190 ms
27,136 KB
testcase_30 AC 156 ms
27,008 KB
testcase_31 AC 225 ms
27,136 KB
権限があれば一括ダウンロードができます

ソースコード

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) {
		} 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;
			}
		}
	}
	for (int i = 0; i < g[a].size(); i++) {
		if (g[a][i] != p) {
			dfs2(g[a][i], a, i);
		} 
	}
}

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));
	}

	int r = 0;

	dfs1(r, -1);
	dfs2(r, -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[r][k]);
	}

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

	cout << res << endl;
}
0