Submission #1202937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202937		byunjaewoo	Star Trek (CEOI20_startrek)	C++20	100 / 100	52 ms	19016 KiB

startrek

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=100010, Mod=1e9+7;
int n, d, dp[N], ep[N], cx[N], cy[N], cnt[N], w[N], c[N], c1, c2, ans0, ans1, rans;
vector<int> adj[N];

void dfs1(int curr, int prev) {
    for(int next:adj[curr]) if(next!=prev) {
        dfs1(next, curr);
        cnt[curr]+=1-dp[next];
        if(!dp[next]) dp[curr]=true;
    }
}

void dfs2(int curr, int prev) {
    for(int next:adj[curr]) if(next!=prev) {
        if(cnt[curr]-(1-dp[next])==0 && !ep[curr]) ep[next]=true;
        dfs2(next, curr);
    }
    w[curr]=dp[curr]|ep[curr];
}

void dfs3(int curr, int prev) {
    cx[curr]=1-dp[curr];
    for(int next:adj[curr]) if(next!=prev) dfs3(next, curr);
    if(dp[curr]) {
        for(int next:adj[curr]) if(next!=prev && !dp[next]) cx[curr]+=cx[next]*(cnt[curr]==1);
    }
    else {
        for(int next:adj[curr]) if(next!=prev) cx[curr]+=cx[next];
    }
}

void dfs4(int curr, int prev) {
    int sum=0, sum2=0;
    for(int next:adj[curr]) {
        if(next!=prev && !dp[next] && cnt[curr]<=2) sum+=cx[next];
        if(next!=prev) sum2+=cx[next];
    }
    for(int next:adj[curr]) if(next!=prev) {
        int tmp=((cnt[curr]-(1-dp[next])+ep[curr])>=1);
        cy[next]=1-tmp;
        if(!tmp || cnt[curr]-(1-dp[next])==0 && ep[curr]) cy[next]+=cy[curr];
        if(!tmp) cy[next]+=sum2-cx[next];
        else if(cnt[curr]-(1-dp[next])==1 && !ep[curr]) cy[next]+=sum-cx[next]*(!dp[next]);
        dfs4(next, curr);
    }
    cy[curr]+=1-w[curr];
    if(!w[curr]) c[curr]=cx[curr]+cy[curr]-1;
    else if(cnt[curr]+ep[curr]>=2) c[curr]=0;
    else if(dp[curr]) c[curr]=cx[curr];
    else c[curr]=cy[curr];
}

int Pow(int a, int b) {
    if(!b) return 1;
    int ret=Pow(a, b/2); ret=(ret*ret)%Mod;
    if(b&1) ret=(ret*a)%Mod;
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>d;
    for(int i=1; i<n; i++) {
        int u, v; cin>>u>>v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    dfs1(1, 0), dfs2(1, 0), dfs3(1, 0), dfs4(1, 0);
    for(int i=1; i<=n; i++) ans0+=w[i];
    for(int i=1; i<=n; i++) c1+=w[i], c2=(c2+c[i]*(1-2*w[i])+Mod)%Mod;
    int tmp=((((n*n)%Mod)*c1)%Mod+(n*c2)%Mod)%Mod; tmp=(tmp*Pow((c2+n*n)%Mod, Mod-2))%Mod;
    ans1=(Pow(Mod-c2, d-1)*(ans0-tmp+Mod))%Mod;
    ans1=(ans1+tmp*Pow(n, 2*d-2))%Mod;
    rans=(c[1]*(Pow(n, 2*d-1)-ans1+Mod))%Mod;
    if(w[1]) rans=(Pow(n, 2*d)-rans+Mod)%Mod;
    cout<<rans;
    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