This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// INOI20_subtree
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
const int MAXN = 100100;
const int MAXE = 150100;
int n, m;
vector<int> adj[MAXN];
int ef[MAXE], eto[MAXE];
int hei[MAXN];
bool iscut[MAXE];
bool mark[MAXN];
vector<int> comp[MAXN];
int cn, cnum[MAXN];
vector<int> tree[MAXN];
int head[MAXN], vpar[MAXN];
int dp[MAXN][2];
int wei[MAXN];
inline void addedge(int x, int y)
{
tree[x].pb(y);
tree[y].pb(x);
}
inline int dfs1(int v, int epar)
{
mark[v] = true;
int dp = hei[v];
for (int e : adj[v]) if (e != epar)
{
int u = eto[e] ^ ef[e] ^ v;
if (mark[u]) dp = min(dp, hei[u]);
else hei[u] = hei[v] + 1, dp = min(dp, dfs1(u, e));
}
if (dp >= hei[v] && epar >= 0) iscut[epar] = true;
return dp;
}
void dfs2(int v)
{
cnum[v] = cn;
comp[cn].pb(v);
for (int e : adj[v]) if (!iscut[e])
{
int u = ef[e] ^ eto[e] ^ v;
if (!cnum[u]) dfs2(u);
}
}
void dfs3(int v)
{
mark[v] = true;
for (int e : adj[v])
{
int u = ef[e] ^ eto[e] ^ v;
if (mark[u]) continue;
if (iscut[e])
{
head[cnum[u]] = u;
vpar[cnum[u]] = v;
}
dfs3(u);
}
}
void dfs4(int v, int par)
{
for (int u : tree[v]) if (u != par)
{
dfs4(u, v);
wei[vpar[u]] = (wei[vpar[u]] * ((ll)dp[u][1] + 1)) % mod;
}
// calc dp
if ((int)comp[v].size() == 1) // single vertex
{
dp[v][0] = dp[v][1] = wei[v];
return;
}
// cycle
int k = (int)comp[v].size();
vector<int> ps(k + 5);
ps[0] = 0;
int cur = 1;
FOR(i, 1, k + 1)
{
cur = (ll)cur * wei[comp[v][i - 1]] % mod;
ps[i] = (ps[i - 1] + cur) % mod;
}
dbgr(ps.begin(), ps.end());
cur = 1;
for (int i = k - 1; i >= 1; i--)
{
dp[v][1] = (dp[v][1] + (ll)ps[i] * cur) % mod;
cur = (ll)cur * wei[comp[v][i]] % mod;
}
dp[v][0] = dp[v][1];
cur = 0;
FOR(i, 1, k)
{
cur = wei[comp[v][i]] * ((ll)cur + 1) % mod;
dp[v][0] = (dp[v][0] + cur) % mod;
}
}
int32_t main(void)
{
fast_io;
cin >> n >> m;
FOR(i, 0, m)
{
cin >> ef[i] >> eto[i];
adj[ef[i]].pb(i);
adj[eto[i]].pb(i);
}
dfs1(1, -1);
dbgr(iscut, iscut + m);
FOR(i, 1, n + 1) if (!cnum[i]) cn++, dfs2(i);
memset(mark, 0, sizeof(mark));
dfs3(1);
head[cnum[1]] = 1;
FOR(i, 0, m) if (iscut[i]) addedge(cnum[ef[i]], cnum[eto[i]]);
FOR(i, 1, cn + 1)
{
rotate(comp[i].begin(), find(all(comp[i]), head[i]), comp[i].end());
}
dbg(cn);
FOR(i, 1, cn + 1)
{
dbg(i);
dbg(head[i]);
dbg(vpar[i]);
dbgr(comp[i].begin(), comp[i].end());
}
fill(wei + 1, wei + n + 1, 1);
dfs4(cnum[1], -1);
dbgr(wei + 1, wei + n + 1);
// FOR(i, 1, cn + 1) cout << "(" << dp[i][0] << ", " << dp[i][1] << ") ";
// cout << endl;
ll ans = 0;
FOR(i, 1, cn + 1) ans = (ans + dp[i][0]) % mod;
ans = (mod + ans % mod) % mod;
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |