제출 #660041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660041		highway_to_hell	Star Trek (CEOI20_startrek)	C++14	100 / 100	532 ms	114972 KiB

startrek

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int mod = 1e9 + 7;
int add(int a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	if (a < 0) a += mod;
	return a;
}
int mul(int a, int b) {
	return 1ll*a*b%mod;
}

const int N = 1e5 + 50, LG = 60;
int n, pw[LG];
ll d;
vector<int> adj[N];
pii dpdw[N], dpup[N], dp[LG][N][2], out[N][2], tmp[N][2]; 

void dfs(int u, int p) {
	int cnt, sum, sbd;
	cnt = sum = sbd = 0;
	for (int v:adj[u]) {
		if(v == p) continue;
		dfs(v, u);
		sum = add(sum, dpdw[v].S);
		sbd = add(sbd, dpdw[v].F*dpdw[v].S);
		cnt += dpdw[v].F;
	}
	dpdw[u].F = !cnt;
	if (cnt >= 2) return;
	dpdw[u].S = (cnt? sbd:sum+1);
}

void sfd(int u, int p) {
	int cnt, sum, sbd;
	cnt = dpup[u].F;
	sum = dpup[u].S;
	sbd = dpup[u].F*dpup[u].S;
	for (int v:adj[u]) {
		if (v == p) continue;
		sum = add(sum, dpdw[v].S);
		sbd = add(sbd, dpdw[v].F*dpdw[v].S);
		cnt += dpdw[v].F;
	}
	for (int v:adj[u]) {
		if (v == p) continue;
		sum = add(sum, -dpdw[v].S);
		sbd = add(sbd, -dpdw[v].F*dpdw[v].S);
		cnt -= dpdw[v].F;
		
		dpup[v].F = !cnt;
		if (cnt < 2) dpup[v].S = (cnt? sbd:sum+1);

		sum = add(sum, dpdw[v].S);
		sbd = add(sbd, dpdw[v].F*dpdw[v].S);
		cnt += dpdw[v].F;

		sfd(v, u);
	}
}

void solve() {
	cin >> n >> d;
	d++;
	for (int i = 1; i <= n-1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	pw[0] = mul(n, n);
	for (int k = 1; k < LG; k++) {
		pw[k] = mul(pw[k-1], pw[k-1]);
	}

	dfs(1, 0);
	sfd(1, 0);
	for (int u = 1; u <= n; u++) {
		if (dpdw[u].F) {
			dp[0][u][dpup[u].F^1] = {1, (dpup[u].F? dpup[u].S : add(dpdw[u].S, dpup[u].S))};
		}
		else {
			dp[0][u][0] = {1, (dpup[u].F ? 0 : dpdw[u].S)};
		}
	}
	for (int k = 1; k < LG; k++) {
		int sum = 0;
		int sa = 0, sb = 0;
		for (int u = 1; u <= n; u++) {
			sum = add(sum, dp[k-1][u][1].F);
			sa = add(sa, dp[k-1][u][0].S);
			sb = add(sb, dp[k-1][u][1].S);
		}
		for (int u = 1; u <= n; u++) {
			dp[k][u][0].F = add(dp[k][u][0].F, mul(dp[k-1][u][0].F, pw[k-1]));
			dp[k][u][0].F = add(dp[k][u][0].F, -mul(dp[k-1][u][0].S, sum));
			dp[k][u][0].F = add(dp[k][u][0].F, mul(dp[k-1][u][1].S, sum));
			dp[k][u][0].S = add(mul(dp[k-1][u][0].S, sa), mul(dp[k-1][u][1].S, sb));

			dp[k][u][1].F = add(dp[k][u][1].F, mul(dp[k-1][u][1].F, pw[k-1]));
			dp[k][u][1].F = add(dp[k][u][1].F, -mul(dp[k-1][u][1].S, sum));
			dp[k][u][1].F = add(dp[k][u][1].F, mul(dp[k-1][u][0].S, sum));
			dp[k][u][1].S = add(mul(dp[k-1][u][1].S, sa), mul(dp[k-1][u][0].S, sb));
		}
	}

	bool flg = 0;
	for (int k = 0; k < LG; k++) {
		if (!(d>>k&1)) continue;
		if (!flg) {
			for (int u = 1; u <= n; u++) {
				out[u][0] = dp[k][u][0];
				out[u][1] = dp[k][u][1];
			}
			flg = 1;
			continue;
		}
		int sum = 0;
		int sa = 0, sb = 0;
		for (int u = 1; u <= n; u++) {
			sum = add(sum, dp[k][u][1].F);
			sa = add(sa, dp[k][u][0].S);
			sb = add(sb, dp[k][u][1].S);
		}
		for (int u = 1; u <= n; u++) {
			tmp[u][0] = tmp[u][1] = {0, 0};

			tmp[u][0].F = add(tmp[u][0].F, mul(out[u][0].F, pw[k]));
			tmp[u][0].F = add(tmp[u][0].F, -mul(out[u][0].S, sum));
			tmp[u][0].F = add(tmp[u][0].F, mul(out[u][1].S, sum));
			tmp[u][0].S = add(mul(out[u][0].S, sa), mul(out[u][1].S, sb));

			tmp[u][1].F = add(tmp[u][1].F, mul(out[u][1].F, pw[k]));
			tmp[u][1].F = add(tmp[u][1].F, -mul(out[u][1].S, sum));
			tmp[u][1].F = add(tmp[u][1].F, mul(out[u][0].S, sum));
			tmp[u][1].S = add(mul(out[u][1].S, sa), mul(out[u][0].S, sb));

			out[u][0] = tmp[u][0];
			out[u][1] = tmp[u][1];
		}
	}
	cout << out[1][0].F << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 15 / 15