Submission #623612

#	Time	Username	Problem	Language	Result	Execution time	Memory
623612		Arinoor	Subtree (INOI20_subtree)	C++17	100 / 100	74 ms	21324 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int par[maxn], h[maxn], U[maxn];
int dp[maxn], val[maxn], val2[maxn], val3[maxn];
bool visited[maxn];
vector<int> G[maxn];

int add(int a, int b){
	int c = a + b;
	if(c >= mod)
		c -= mod;
	if(c < 0)
		c += mod;
	return c;
}

int mul(int a, int b){
	return 1ll * a * b % mod;
}

void dfs(int v){
	visited[v] = true;
	for(int u : G[v]){
		if(!visited[u]){
			par[u] = v;
			h[u] = h[v] + 1;
			dfs(u);
		}
		else if(h[v] < h[u]){
			U[v] = u;
		}
	}
}

void Dfs(int v){
	for(int u : G[v])
		if(par[u] == v)
			Dfs(u);
	if(!U[v]){
		dp[v] = 1;
		for(int u : G[v])
			if(par[u] == v)
				dp[v] = mul(dp[v], add(dp[u], 1));
		return;
	}
	vector<int> V;
	V.pb(0);
	int u = U[v];
	while(true){
		V.pb(u);
		if(u == v)
			break;
		u = par[u];
	}
	int m = V.size();
	val[0] = 1;
	for(int i = 1; i < m; i ++){
		val[i] = 1;
		int v = V[i];
		for(int u : G[v])
			if(par[u] == v and u != V[i - 1])
				val[i] = mul(val[i], add(dp[u], 1));
	}
	val2[0] = 1;
	for(int i = 1; i < m; i ++)
		val2[i] = mul(val2[i - 1], val[i]);
	val3[m - 1] = val[m - 1];
	for(int i = m - 2; ~i; i --)
		val3[i] = mul(val3[i + 1], val[i]);
	for(int i = m - 2; ~i; i --)
		val3[i] = add(val3[i], val3[i + 1]);
	for(int i = 0; i < m - 2; i ++)
		dp[v] = add(dp[v], mul(val2[i], val3[i + 2]));
}

int main(){
	ios;
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i ++){
		int u, v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1);
	Dfs(1);
	int ans = 0;
	for(int i = 1; i <= n; i ++){
		ans = add(ans, dp[i]);
	}
	cout << ans << '\n';
}

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