Submission #1116500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116500		Thunnus	Star Trek (CEOI20_startrek)	C++17	100 / 100	97 ms	18828 KiB

startrek

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
const int MAX_N = 1e5;
const int MAX_D = 1e5;
const int MOD = 1e9 + 7;
bool canWin[MAX_N + 1];
int countChildrenLosers[MAX_N + 1], critical[MAX_N + 1], sumCriticalW[MAX_N + 1], sumCriticalL[MAX_N + 1], dp[MAX_D];
vector<int> adj[MAX_N + 1];
 
void dfsGame( int u, int p ) {
    canWin[u] = false;
    countChildrenLosers[u] = 0;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfsGame( v, u );
        canWin[u] |= !canWin[v];
        countChildrenLosers[u] += !canWin[v];
    }
}
 
void calcCritical( int u ) {
    if ( canWin[u] ) {
        if ( countChildrenLosers[u] >= 2 )
            critical[u] = 0;
        else
            critical[u] = sumCriticalL[u];
    } else
        critical[u] = sumCriticalW[u] + 1;
}
 
void dfsCritical( int u, int p ) {
    sumCriticalW[u] = sumCriticalL[u] = 0;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfsCritical( v, u );
        if ( canWin[v] )
            sumCriticalW[u] += critical[v];
        else
            sumCriticalL[u] += critical[v];
    }
    calcCritical( u );
}
 
void reroot( int u, int v ) {
    if ( canWin[v] )
        sumCriticalW[u] -= critical[v];
    else {
        sumCriticalL[u] -= critical[v];
        countChildrenLosers[u]--;
    }
    canWin[u] = (countChildrenLosers[u] > 0);
    calcCritical( u );
 
    if ( canWin[u] )
        sumCriticalW[v] += critical[u];
    else {
        sumCriticalL[v] += critical[u];
        countChildrenLosers[v]++;
    }
    canWin[v] = (countChildrenLosers[v] > 0);
    calcCritical( v );
}
 
int l = 0, c = 0;
void dfs( int u, int p ) {
    l += !canWin[u];
    c += (canWin[u] ? 1 : -1) * critical[u];
 
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
 
        reroot( u, v );
        dfs( v, u );
        reroot( v, u );
    }
}
 
int lgPut( int x, int n ) {
    if ( n == 0 )
        return 1;
 
    int p = lgPut( x, n / 2 );
    p = (long long)p * p % MOD;
    if ( n % 2 == 1 )
        p = (long long)p * x % MOD;
 
    return p;
}
 
int a, b;
int calcDp( int n ) {
    if ( n == 0 )
        return 1;
    if ( n % 2 == 1 )
        return (lgPut( a, n ) + b * calcDp( n - 1 )) % MOD;
 
    int x = calcDp( n / 2 );
    x = (x * (lgPut( a, n / 2 ) + lgPut( b, n / 2)) % MOD - lgPut( a, n / 2 ) * lgPut( b, n / 2 ) % MOD + MOD) % MOD;
    return x;
}
 
signed main() {
    int n, d;
 
    cin >> n >> d;
 
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }
 
    dfsGame( 1, 0 );
    dfsCritical( 1, 0 );
    dfs( 1, 0 );
 
    a = n * n % MOD;
    b = c;
    while ( b < 0 )
        b += MOD;
 
    int dpd = calcDp( d - 1 );
    dpd = dpd * l % MOD;
 
    dfsGame( 1, 0 );
    dfsCritical( 1, 0 );
    if ( canWin[1] )
        cout << (lgPut( n, 2 * d ) - dpd * critical[1] % MOD + MOD) % MOD;
    else
        cout << dpd * critical[1] % MOD << "\n";
 
    return 0;
}

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