結果

問題 No.1075 木の上の山
ユーザー ats5515ats5515
提出日時 2020-06-05 22:00:06
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,341 bytes
コンパイル時間 1,645 ms
コンパイル使用メモリ 160,852 KB
実行使用メモリ 27,352 KB
最終ジャッジ日時 2023-08-22 15:25:35
合計ジャッジ時間 7,429 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 407 ms
27,192 KB
testcase_18 AC 178 ms
27,260 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

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