Submission #390070

#	Time	Username	Problem	Language	Result	Execution time	Memory
390070		talant117408	Star Trek (CEOI20_startrek)	C++17	7 / 100	3 ms	2764 KiB

startrek

/*
    Code written by Talant I.D.
*/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
 
const int mod = 1e9+7;
 
ll mode(ll a) {
    a %= mod;
    if (a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b) {
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b) {
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b) {
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 1e5+7;
bool state[N];
int losing_children[N], critical;
vector <int> graph[N];

bool dfs(int v, int p) {
	losing_children[v] = 0;
	int cnt = 0, children = 0;
	for (auto to : graph[v]) {
		if (to == p) continue;
		children++;
		dfs(to, v);
		cnt += (state[to] ? 1 : 0);
		if (!state[to]) losing_children[v]++;
	}
	if (children == 0) state[v] = 1;
	else if (cnt) state[v] = 0;
	else state[v] = 1;
	return state[v];
}

void dfs2(int v, int p) {
	if (state[v] == 0) {
		if (losing_children[v] > 1) return;
		critical++;
	}
	else if (v == 1) {
		critical++;
	}
	for (auto to : graph[v]) {
		if (to == p) continue;
		dfs2(to, v);
	}
}

int main() {
	do_not_disturb
	
	int n;
	ll d;
	cin >> n >> d;
	for (int i = 0; i < n-1; i++) {
		int x, y;
		cin >> x >> y;
		graph[x].pb(y);
		graph[y].pb(x);
	}
	
	if (n == 2) {
		cout << binpow(2, d*2);
	}
	else if (d == 1) {
		dfs2(1, 1);
		ll l = 0, w = 0;
		for (int i = 1; i <= n; i++) {
			dfs(i, i);
			if (state[i]) l++;
			else w++;
		}
		dfs(1, 1);
		if (state[1]) cout << critical*l;
		else cout << n*w+(n-critical)*l;
	}
	
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 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