Submission #633508

#	Time	Username	Problem	Language	Result	Execution time	Memory
633508		MatBad	Subtree (INOI20_subtree)	C++14	12 / 100	482 ms	1048576 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=a; i<=b; i++)
#define FORR(i, a, b) for(int i=a; i>=b; i--)
#define pb push_back
#define ppb pop_back
#define lc 2*u
#define rc 2*u+1
#define mid ((l+r)/2)
#define F first
#define S second
#define debug(x) cerr<<"$ "<<#x<<" : "<<x<<"$\n"
#define wall() cerr<<"\n----------------------\n"

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

const ll MX=1e5+5, M=1e9+5, LG=19, inf=1e9+5, MOD=1e9+7;

ll n, m, dp[2][MX];
vector<int> adj[MX];

void dfs(int u, int p){
	dp[1][u]=1;
	for(int v:adj[u])if(v!=p){
		dfs(v, u);
		dp[0][u] = (dp[0][u]+dp[0][v]+dp[1][v])%MOD;
		dp[1][u] = dp[1][u]*(dp[1][v]+1)%MOD;
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	FOR(i, 1, m) {
		int u, v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1, 0);
	cout<<(dp[0][1]+dp[1][1])%MOD<<'\n';
}

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