Submission #882078

#	Time	Username	Problem	Language	Result	Execution time	Memory
882078		vjudge1	Star Trek (CEOI20_startrek)	C++17	38 / 100	52 ms	17252 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, k[2], sz[N];
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) {
	sz[u] = 1;
	for (auto i: g[u])
		if (i != par) {
			dfs1(i, u);
			dpd[u] |= dpd[i];
			sz[u] += sz[i];
		}
	dpd[u] = !dpd[u];
}
 
void dfs2(int u, int par, int c) {
	c -= dpd[u];
	dp[u] = (c != 0);
	c = (u == 0)? 0 : !dp[u];
	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) {
	int c = 0, v = 0;
	for (auto i: g[u])
		if (i != par) {
			dfs3(i, u);
			c += dpd[i];
			if (dpd[i])
				v = i;
		}
	if (!c) {
		for (auto i: g[u])
			if (i != par) {
				res[u].F += res[i].S;
				res[u].S += res[i].F;
			}
		res[u].F += k[1];
		res[u].S += k[0];
	}
	else if (c == 1) {
		res[u].F = (sz[u] - sz[v]) * n + res[v].S;
		res[u].S = res[v].F;
	}
	else 
		res[u].F = sz[u] * n;
}
 
void solve() {
	if (d == 1) {
		dfs1(0, 0);
		dp[0] = 1;
		dfs2(0, 0, 2);
		for (int i = 0; i < n; i++) {
			dp[i] &= dpd[i];
			k[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: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15