Submission #470184

#	Time	Username	Problem	Language	Result	Execution time	Memory
470184		AmirrezaM	Subtree (INOI20_subtree)	C++14	100 / 100	171 ms	23888 KiB

Main

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

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

#define vc vector
#define pb push_back

const int MAXN = 1e5 + 15 , mod = 1e9 + 7;

int n , m, go[MAXN] , lw[MAXN] , h[MAXN] , par[MAXN] , mark[MAXN];
vc<int> adj[MAXN];

int dp[MAXN] , chMul[MAXN] , ps[MAXN];

void dfs(int v , int p = -1){
  par[v] = p;
  mark[v] = 1;
  go[v] = -1 , lw[v] = MAXN;
  for(int u : adj[v]){
	if(mark[u] == 0){
	  h[u] = h[v] + 1;
	  dfs(u , v);
	  if(lw[u] <= h[v]) go[v] = u;
	  lw[v] = min(lw[v] , lw[u]);
	}
	else if(u != p and mark[u] == 1) lw[v] = h[u];
  }
  mark[v] = 2;
}
void dfsCalc(int v){
  mark[v] = 0;
  for(int u : adj[v]){
	if(mark[u] == 2) dfsCalc(u);
  }
  if(lw[v] == h[v]){
	vc<int> c;
	for(int u = v ; u > -1 ; u = go[u]){
	  c.pb(u);
	}
	
	int ml = 1 , sm = 0;
	for(int u : c){
	  chMul[u] = 1;
	  for(int k : adj[u]){
		if(par[k] == u and k != go[u]){
		  chMul[u] = (1ll * chMul[u] * (dp[k] + 1)) % mod;
		}
	  }
	  ml = (1ll * ml * chMul[u]) % mod;
	  sm += ml;
	  if(sm >= mod) sm -= mod;
	  ps[u] = sm;
	}
	
	ml = 1 , sm = 0;
	for(int i = c.size()-1 ; i >= 1 ; i--){
	  int u = c[i];
	  dp[v] = (dp[v] + 1ll * ps[par[u]] * ml) % mod;
	  ml = (1ll * ml * chMul[u]) % mod;
	}
  }
  else{
	dp[v] = 1;
	for(int u : adj[v]){
	  if(par[u] != v) continue;
	  dp[v] = (1ll * dp[v] * (dp[u] + 1)) % mod;
	}
  }
}

int main(){
  cin >> n >> m;
  for(int i = 0 ; i < m ; i++){
	int s , e;
	cin >> s >> e;
	s-- , e--;
	adj[s].pb(e) , adj[e].pb(s);
  }
  dfs(0);
  dfsCalc(0);
  int ans = 0;
  for(int i = 0 ; i < n ; i++){
	ans += dp[i];
	if(ans >= mod) ans -= mod;
  }
  cout << ans << endl;
}

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