Submission #336774

#TimeUsernameProblemLanguageResultExecution timeMemory
336774dolphingarlicStar Trek (CEOI20_startrek)C++14
38 / 100
95 ms16364 KiB
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll MOD = 1e9 + 7;

vector<int> graph[100001];
ll win_as_root[100001], critical[100001];

void dfs1(int node = 1, int parent = 0) {
    for (int i : graph[node]) if (i != parent) {
        dfs1(i, node);
        win_as_root[node] += (win_as_root[i] == 0);
    }
    if (!win_as_root[node]) critical[node] = 1;
    for (int i : graph[node]) if (i != parent) {
        if ((win_as_root[node] == 1 && !win_as_root[i]) || !win_as_root[node])
            critical[node] += critical[i];
    }
}

void dfs2(int node = 1, int parent = 0, int anc = 1) {
    win_as_root[node] += (anc == 0);
    for (int i : graph[node]) if (i != parent) {
        dfs2(i, node, win_as_root[node] - (win_as_root[i] == 0));
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, d;
    cin >> n >> d;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs1();
    dfs2();

    ll lose_cnt = 0;
    for (int i = 1; i <= n; i++) lose_cnt += (win_as_root[i] == 0);
    if (win_as_root[1])
        cout << (n * n - lose_cnt * critical[1]) % MOD;
    else
        cout << lose_cnt * critical[1] % MOD;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...