Submission #634712

#	Time	Username	Problem	Language	Result	Execution time	Memory
634712		S2speed	Subtree (INOI20_subtree)	C++17	100 / 100	127 ms	35456 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 2e5 + 17 , md = 1e9 + 7 , inf = 2e16;

ll n , m , ans;
bitset<maxn> mark;
vector<ll> adj[maxn] , cc[maxn] , st , del;
vector<pll> cdj[maxn];
ll c[maxn] , o , dp[maxn] , ps[maxn] , pz[maxn];

void cDFS(ll r , ll par){
	st.push_back(r);
	mark[r] = true;
	for(auto i : adj[r]){
		if(i == par) continue;
		if(mark[i]){
			if(c[r] != -1) continue;
			while(st.back() != i){
				c[st.back()] = o;
				cc[o].push_back(st.back());
				del.push_back(st.back());
				st.pop_back();
			}
			c[i] = o;
			cc[o].push_back(i);
			o++;
			while(!del.empty()){
				st.push_back(del.back());
				del.pop_back();
			}
			continue;
		}
		cDFS(i , r);
	}
	st.pop_back();
	return;
}

ll cal(vector<ll> &v , ll l , ll r){
	if(l >= r) return 0;
	if(r - l == 1) return v[l];
	ll m = (r + l) >> 1;
	ll a = 1 , b = 1 , h = 1;
	for(ll i = m - 1 ; i >= l ; i--){
		h *= v[i]; h %= md;
		a += h;
	}
	h = 1;
	for(ll i = m + 1 ; i < r ; i++){
		h *= v[i]; h %= md;
		b += h;
	}
	a %= md; b %= md;
	ll res = cal(v , l , m) + cal(v , m + 1 , r) + a * b % md * v[m];
	return res % md;
}

void dDFS(ll r , ll t , ll par , bool f = false){
//	cout<<r<<' '<<t<<' '<<par<<' '<<f<<endl;
	if(r < n){
		ll h = 1;
		for(auto p : cdj[r]){
			ll i = p.first , u = p.second;
			if(i == par) continue;
			dDFS(i , u , r);
			h *= dp[i] + 1; h %= md;
		}
		dp[r] = h;
		ans += h;
		return;
	}
	swap(r , t);
	if(f){
		ll h = 1;
		for(auto i : adj[r]){
			ll u = (c[i] == -1 ? i : c[i]);
			if(u == t || u == par) continue;
			dDFS(u , i , t);
			h *= dp[u] + 1; h %= md;
		}
		dp[r] = h;
		return;
	}
	ll ind = -1 , sz = sze(cc[t]);
	for(ll i = 0 ; i < sz ; i++){
		if(cc[t][i] == r){
			ind = i;
			break;
		}
	}
	vector<ll> v;
	for(ll i = ind + 1 ; i < sz ; i++){
		dDFS(t , cc[t][i] , par , true);
		v.push_back(dp[cc[t][i]]);
	}
	for(ll i = 0 ; i < ind ; i++){
		dDFS(t , cc[t][i] , par , true);
		v.push_back(dp[cc[t][i]]);
	}
	ll vs = sz - 1 , z;
	dDFS(t , r , par , true);
	z = dp[r];
	ps[0] = v[0] + 1;
	pz[0] = v[0];
	for(ll i = 1 ; i < vs ; i++){
		pz[i] = pz[i - 1] * v[i] % md;
		ps[i] = ps[i - 1] + pz[i]; ps[i] -= (ps[i] >= md) * md;
	}
	ll cur = 1 , res = 0;
	for(ll i = vs - 1 ; i > 0 ; i--){
		ll h = cur * ps[i - 1] % md;
		res += h;
		cur *= v[i]; cur %= md;
	}
	res += cur;
	dp[t] = res % md * z % md;
	ans += dp[t];
	ans += cal(v , 0 , vs);
	return;
}

/*
9 11
1 2 2 3 3 1
4 5 5 6 6 4
7 8 8 9 9 7
1 4 1 7
*/

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	memset(c , -1 , sizeof(c));
	cin>>n>>m; o = n;
	for(ll i = 0 ; i < m ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
	}
	cDFS(0 , -1);
	for(ll i = 0 ; i < n ; i++){
		ll v = (c[i] == -1 ? i : c[i]);
		for(auto j : adj[i]){
			ll u = (c[j] == -1 ? j : c[j]);
			if(v == u) continue;
			cdj[v].push_back({u , j});
		}
	}
	dDFS((c[0] == -1 ? 0 : c[0]) , 0 , -1);
	ans %= md;
	cout<<ans<<'\n';
	return 0;
}

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