Submission #1188811

#TimeUsernameProblemLanguageResultExecution timeMemory
118881112345678Star Trek (CEOI20_startrek)C++20
0 / 100
2 ms2632 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int nx=1e5+5, mod=1e9+7; ll n, k, u, v, dp[nx], dpr[nx], lvl[nx], force[nx], lcnt, res; vector<int> d[nx]; void dfs(int u, int p) { lvl[u]=lvl[p]+1; for (auto v:d[u]) if (v!=p) dfs(v, u), dp[u]|=!dp[v]; } void fillforce(int u, int p) { int cnt=0; if (!dp[u]) { for (auto v:d[u]) if (v!=p) cnt++; if (cnt==1) for (auto v:d[u]) if (v!=p) force[v]=1, fillforce(v, u); } else { for (auto v:d[u]) if (v!=p&&!dp[v]) cnt++; if (cnt==1) for (auto v:d[u]) if (v!=p&&!dp[v]) force[v]=1, fillforce(v, u); } } void dfs2(int u, int p) { lcnt+=!(dp[u]|dpr[u]); //cout<<"debug "<<u<<' '<<dp[u]<<' '<<dpr[u]<<'\n'; int cnt=0; for (auto v:d[u]) if (v!=p&&!dp[v]) cnt++; for (auto v:d[u]) { if (v==p) continue; if (cnt-!dp[v]) dpr[v]=1; dfs2(v, u); } } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>k; for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u); dfs(1, 1); force[1]=1; fillforce(1, 1); dfs2(1, 1); //cout<<"lcnt "<<lcnt<<'\n'; for (int i=1; i<=n; i++) { if (lvl[i]%2) { if (dp[i]) res=(res+n)%mod; else { if (force) res=(res+lcnt)%mod; } } else { if (!dp[i]) { if (force) res=(res+(n-lcnt))%mod; else res=(res+n)%mod; } } //cout<<i<<' '<<res<<'\n'; } cout<<res; }
#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...