제출 #881478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881478		vjudge1	Star Trek (CEOI20_startrek)	C++17	0 / 100	3 ms	4204 KiB

startrek

// In the Name of Allah

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
#define unq(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())

const int N = 1e5 + 12, mod = 1'000'000'000 + 7;
vector<int> g[N];
int n, d, c[2];
bool dpd[N], dp[N];
pii res[N];

void ip() {
	cin >> n >> d;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
}

void dfs1(int u, int par) {
	for (auto i: g[u])
		if (i != par) {
			dfs1(i, u);
			dpd[u] |= dpd[i];
		}
	dpd[u] = !dpd[u];
}

void dfs2(int u, int par, int c) {
	c -= !dpd[u];
	dp[u] = !c;
	if (u)
		c = !dp[par];
	else if (g[u].size() == 1)
		c = 1;
	else
		c = 0;
	for (auto i: g[u])
		if (i != par)
			c += !dpd[i];
	for (auto i: g[u])
		if (i != par)
			dfs2(i, u, c);
}

void dfs3(int u, int par) {
	if (dpd[u]) {
		res[u].F += c[1];
		res[u].S += c[0];
	}
	else 
		res[u].F += n;
	for (auto i: g[u])
		if (i != par) {
			dfs3(i, u);
			res[u].F += res[i].S;
			res[u].S += res[i].F;
		}
}

void solve() {
	if (d == 1) {
		dfs1(0, 0);
		dfs2(0, 0, !dpd[0]);
		for (int i = 0; i < n; i++) {
			dp[i] &= dpd[i];
			c[dp[i]]++;
		}
		dfs3(0, 0);
		cout << res[0].F % mod;
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), solve();
	return 0;
}

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