Submission #975108

#	Time	Username	Problem	Language	Result	Execution time	Memory
975108		efedmrlr	Star Trek (CEOI20_startrek)	C++17	45 / 100	63 ms	17460 KiB

startrek

#include <bits/stdc++.h>

#define int long long int
#define lli int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int MOD = 1e9 + 7;

int add(int x, int y) {
    if(x + y >= MOD) return x + y - MOD;
    return x + y;
}
int mult(int x, int y) {
    return (int)((1ll * x * y) % MOD);
}
int subt(int x, int y) {
    if(x - y < 0) return x - y + MOD;
    return x - y;
}
int fp(lli x, lli y) {
    lli ret = 1;
    while(y > 0ll) {
        if(y & 1ll) {
            ret = mult(ret, x);
        }
        x = mult(x, x);
        y /= 2ll;
    }
    return ret;
}
vector<bool> dp(N, 0), dpp(N, 0);
vector<vector<int> > adj(N, vector<int>());
vector<bool> dep(N, 0);
vector<int> sub(N, 0);
lli n, d;

void dfsdp(int node, int par) {
    sub[node] = 1;
    for(auto c : adj[node]) {
        if(c == par) continue;
        dep[c] = !dep[node];
        dfsdp(c, node);   
        sub[node] += sub[c];

        if(!dp[c]) dp[node] = 1;
    }

}
void dfsdpp(int node, int par) {
    bool f = 0;
    for(auto c : adj[node]) {
        if(c == par) continue;
        if(!dpp[node]) dpp[c] = 1;
        if(f) dpp[c] = 1;
        if(!dp[c]) f = 1;
    }
    f = 0;
    for(int i = adj[node].size() - 1; i>=0; i--) {
        auto c = adj[node][i];
        if(c == par) continue;
        if(f) dpp[c] = 1;
        if(!dp[c]) f = 1;
    }
    for(auto c : adj[node]) {
        if(c == par) continue;
        dfsdpp(c, node);
    }
}
int ans = 0, win = 0;
void dfswin(int node, int par) {
    int lcnt = 0;
    if(!dep[node]) {
        for(auto c : adj[node]) {
            if(c == par) continue;
            if(!dp[c]) lcnt++;
        }
        if(lcnt > 1) {
            ans = add(ans, mult(sub[node], n));
            return;
        }
        else {
            for(auto c : adj[node]) {
                if(c == par || dp[c]) continue;
                ans = add(ans, mult(sub[node] - sub[c], n));
                dfswin(c, node);
            }
            return;
        }
    }
    else {
        ans = add(ans, n - win);
        for(auto c : adj[node]) {
            if(c == par) continue;
            dfswin(c, node);
        }
    }

}
void dfslose(int node, int par) {
    if(!dep[node]) {
        ans = add(ans, win);
        for(auto c : adj[node]) {
            if(c == par) continue;
            dfslose(c, node);
        }
    }
    else {
        int lcnt = 0;
        for(auto c : adj[node]) {
            if(c == par) continue;
            if(!dp[c]) lcnt++;
        }
        if(lcnt > 1) {
            return;
        }
        else {
            for(auto c : adj[node]) {
                if(c == par || dp[c]) continue;
                dfslose(c, node);
            }
        }
    }
}

void solve() {
    cin >> n >> d;
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    if(n == 2) {
        cout << fp(4, d) << "\n";
        return;
    }

    dfsdp(1, 0);
    dpp[1] = 1;
    dfsdpp(1, 0);
    // for(int i = 1; i <= n; i++) {
    //     cout << "i: " << i << " dpp: " << dpp[i] << "\n";
    // }
    for(int i = 1; i <= n; i++) {
        if(i != 1 && dpp[i] == 0) {
            dpp[i] = 1;
        }
        else {
            dpp[i] = 0;
        }
        for(auto c : adj[i]) {
            if(!dp[c]) dpp[i] = 1;
        }
        win += !dpp[i];
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << "i:" << i << " dp:" << dp[i] << " dpp:" << dpp[i] << "\n";
    // }
    if(dpp[1]) {
        dfswin(1, 0);
    }
    else {
        dfslose(1, 0);
    }
    cout << ans << "\n";
}

signed main() {
    fastio();
    solve();
}

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