Submission #659599

#	Time	Username	Problem	Language	Result	Execution time	Memory
659599		Lobo	Star Trek (CEOI20_startrek)	C++17	23 / 100	1072 ms	51800 KiB

startrek

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 5e5+10;
const int mod = 1e9+7;

int n, d, dpw[maxn][2], dpl[maxn][2], dpwup[maxn][2], dplup[maxn][2];
vector<int> g[maxn];
int SL, SW, SL0, SW0, SWb, SLb;

void dfs1(int u, int ant) {
    dpw[u][1] = SW*dpw[u][0] + SL*(dpw[u][0]+dpl[u][0]); dpw[u][1]%= mod;
    dpl[u][1] = SW*dpl[u][0]; dpl[u][1]%= mod;

    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        qtl+= dpl[v][0];
        dfs1(v,u);
    }

    for(auto v : g[u]) if(v != ant) {
        qtl-= dpl[v][0];
        if(qtl) {
            dpw[u][1]+= dpw[v][1]+dpl[v][1]; dpw[u][1]%= mod;
            dpl[u][1]+= 0;
        }
        else {
            dpw[u][1]+= dpl[v][1]; dpw[u][1]%= mod;
            dpl[u][1]+= dpw[v][1]; dpl[u][1]%= mod;
        }
        qtl+= dpl[v][0];
    }
}

map<int,int> wp[maxn];
int solwp(int u, int ant) {
    if(wp[u].count(ant)) return wp[u][ant];
    wp[u][ant] = 0;
    for(auto v : g[u]) if(v != ant) {
        if(solwp(v,u) == 0) wp[u][ant] = 1;
    }
    return wp[u][ant];
}

// void dfs0(int u, int ant) {
//     dpw[u][0] = 0;
//     for(auto v : g[u]) if(v != ant) {
//         dfs0(v,u);
//     }
//     for(auto v : g[u]) if(v != ant) {
//         if(solwp(v,u) == 0) dpw[u][0] = 1;
//     }
//     dpl[u][0] = 1-dpw[u][0];
// }

void dfs0(int u, int ant) {
    dpw[u][0] = 0;
    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        dfs0(v,u);
        qtl+= dpl[v][0];
    }

    if(qtl) dpw[u][0] = 1;
    dpl[u][0] = 1-dpw[u][0];
}

void dfs0up(int u, int ant) {
    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        qtl+= dpl[v][0];
    }

    for(auto v : g[u]) if(v != ant) {
        qtl-= dpl[v][0];
        if(qtl || dpwup[u][0]) {
            dpwup[v][0] = 0;
            dplup[v][0] = 1-dpwup[v][0];
        }
        else {
            dpwup[v][0] = 1;
            dplup[v][0] = 1-dpwup[v][0];
        }
        qtl+= dpl[v][0];
    }

    for(auto v : g[u]) if(v != ant) {
        dfs0up(v,u);
    }
}

int dpwc[maxn], dplc[maxn], dpwupc[maxn], dplupc[maxn];
void dfscnt(int u, int ant, int b) {
    dpwc[u] = 0;
    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        dfscnt(v,u,b);
        qtl+= dplc[v];
    }

    if(qtl || u == b) dpwc[u] = 1;
    dplc[u] = 1-dpwc[u];
}

void dfscntup(int u, int ant, int b) {
    int qtl = 0;
    for(auto v : g[u]) if(v != ant) {
        qtl+= dplc[v];
    }

    for(auto v : g[u]) if(v != ant) {
        qtl-= dplc[v];
        if((qtl || dpwupc[u]) && v != b) {
            dpwupc[v] = 0;
            dplupc[v] = 1-dpwupc[v];
        }
        else {
            dpwupc[v] = 1;
            dplupc[v] = 1-dpwupc[v];
        }
        qtl+= dplc[v];
    }

    for(auto v : g[u]) if(v != ant) {
        dfscntup(v,u,b);
    }
}
void solve() {
    cin >> n >> d;

    for(int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs0(1,0);
    dpwup[1][0] = 0;
    dplup[1][0] = 1;
    dfs0up(1,0);
    for(int i = 1; i <= n; i++) {
        if(dpw[i][0] || dpwup[i][0]) SW0++;
        else SL0++;
    }

    for(int i = 1; i <= n; i++) {
        dfscnt(1,0,i);
        if(i == 1) {
            dpwupc[1] = 1;
            dplupc[1] = 0;
        }
        else {
            dpwupc[1] = 0;
            dplupc[1] = 1;
        }
        dfscntup(1,0,i);
        for(int j = 1; j <= n; j++) {
            if(dpwc[j] || dpwupc[j]) SWb++;
            else SLb++; 
        }
    }


    // cout << SWb << " " << SLb << endl;
    SWb%= mod;
    SLb%= mod;
    SW = SW0;
    SL = SL0;
    for(int i = 1; i <= d-1; i++) {
        int newSW = SW*SW0 + SL*SWb; newSW%= mod;
        int newSL = SW*SL0 + SL*SLb; newSL%= mod;
        SW = newSW;
        SL = newSL;
    }

    dfs1(1,0);

    cout << dpw[1][1] << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

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