Submission #1188825

#TimeUsernameProblemLanguageResultExecution timeMemory
118882512345678Star Trek (CEOI20_startrek)C++20
0 / 100
1 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, tot=0; for (auto v:d[u]) if (v!=p) tot++; for (auto v:d[u]) if (v!=p&&dp[v]) cnt++; //cout<<"tot "<<cnt<<' '<<tot<<'\n'; for (auto v:d[u]) { if (v==p) continue; if (!dpr[u]&&(cnt-dp[v])==tot-1) 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'; if (dp[1]) { for (int i=1 ;i<=n; i++) { if (!force[i]) res=(res+n)%mod; else if (lvl[i]%2) res=(res+n)%mod; else res=(res+(n-lcnt))%mod; } } else { for (int i=1; i<=n ;i++) { if (!force[i]) continue; if (lvl[i]%2) res=(res+lcnt)%mod; } } cout<<res; } /* 5 1 1 2 1 3 3 4 3 5 */
#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...