Submission #1046186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046186		javotaz	Subtree (INOI20_subtree)	C++17	100 / 100	57 ms	34904 KiB

Main

// In the Name of Allah
 
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")
 
typedef long long ll;
 
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7, N = 1e5 + 12;
vector<int> g[N], e[N];
int n, m, tc, c[N], h[N];
ll ans, dp[N];
bool mrk[N];

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

pii dfs1(int u, int par = -1) {
	mrk[u] = true;
	pii res = {-1, n};
	for (auto i: g[u])
		if (i != par) {
			if (mrk[i]) { 
				if (!c[i])
					res = {++tc, h[i]};
			}
			else {
				h[i] = h[u] + 1;
				pii tmp = dfs1(i, u);
				if (tmp.S <= h[u])
					res = tmp;
			}
		}
	if (res.S > h[u]) 
		c[u] = ++tc;
	else
		c[u] = res.F;
	e[c[u]].pb(u);
	return res;
}

int bp(int x, int y) {
    if (y < 2) return y? x : 1;
    ll tmp = bp(x, y / 2);
    tmp = tmp * tmp % mod;
    return (y & 1)? tmp * x % mod : tmp;
}

void dfs(int u, int par = -1) {
	vector<ll> v;
	int sz = e[u].size(), t = -1;
	for (auto i: e[u]) {
		ll x = 1;
		for (auto j: g[i])
			if (c[j] != par && c[j] != u) {
				dfs(c[j], u);
				x = (x * (dp[c[j]] + 1)) % mod;
			}
			else if (c[j] == par)
				t = v.size();
		v.pb(x);
	}
	if (t != -1) {
		vector<ll> z(sz), p(sz);
		for (int i = t; i < sz; i++)
			z[i - t] = v[i];
		for (int i = 0; i < t; i++)
			z[sz - t + i] = v[i];
		p[0] = 1;
		for (int j = 1; j < sz - 1; ++j) {
			ll i = z[j];
			p[j] = (p[j - 1] * i) % mod;
		}
		for (int j = 1; j < sz - 1; ++j)
			p[j] = (p[j] + p[j - 1]) % mod;
		reverse(z.begin() + 1, z.end());
		ll x = 1;
		for (int j = 0; j < sz - 1; ++j) {
			ll i = z[j];
			x = (x * i) % mod;
			dp[u] = (dp[u] + x * p[sz - j - 2]) % mod;
		}
		if (sz == 1)
			dp[u] = z[0];
	}
	ll val = 0, x = 1;
	for (int i = 0; i < sz - 1; i++) {
		x = (x * v[i]) % mod;
		val += x;
	}
	val %= mod;
	ans += val;
	for (int i = 1; i < sz; i++) {
		int ls = (i - 2 + sz) % sz;
		val = (val * bp(v[i - 1], mod - 2) + mod - 1) % mod;
		x = (x * bp(v[i - 1], mod - 2)) % mod;
		x = (x * v[ls]) % mod;
		val = (val + x) % mod;
		ans += val;
	}
	ans %= mod;
	if (sz == 1)
		ans = (ans + v[0]) % mod;
}

void solve() {
	dfs1(0);
	dfs(1);
	cout << ans;
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), solve();
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50