Submission #1041983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041983		PM1	Subtree (INOI20_subtree)	C++17	100 / 100	31 ms	21588 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=1e5+5,M=1e9+7;
int n,m,par[mxn],h[mxn],dis[mxn],mark[mxn];
vector<int>v[mxn];
ll dp[mxn][2][2][2],ans=0;
void dfs(int z){
	mark[z]=1;
	ll res=1;
	int c=0;
	for(auto i:v[z]){
		if(par[z]!=i && !mark[i]){
			par[i]=z;
			dis[i]=dis[z]+1;
			dfs(i);
			if(h[i]>dis[z] || h[i]==0){
				res*=(dp[i][1][1][0]+1);
				res%=M;
			}
			else{
				c=i;
				h[z]=h[i];
			}
		}
		else if(mark[i] && par[z]!=i && h[z]==0){
			h[z]=dis[i];
		}
	}
	if(c==0){
		dp[z][1][1][0]=res;
		dp[z][0][0][0]=1;
		ans+=dp[z][1][1][0];
		ans%=M;
		//cout<<"F"<<" "<<z<<" "<<ans<<'\n';
		return ;
	}
	dp[z][0][0][0]=1;
	dp[z][0][1][0]=((dp[c][0][0][0]+dp[c][0][1][0])*res)%M;
	//dp[z][0][0][1]=(dp[c][0][0][1]+dp[0][1][0])%M;
	dp[z][1][1][0]=(dp[c][1][1][0]*res)%M;
	dp[z][1][0][0]=(dp[c][1][1][0]+dp[c][1][0][0])%M;
	dp[z][1][1][1]=((dp[c][1][1][1]+dp[c][1][0][0])*res)%M;
	ans+=dp[z][1][1][0]+dp[z][0][1][0];
	if(h[z]==dis[z]){
		ans+=dp[z][1][1][1];
		ans-=dp[z][1][1][0];
		dp[z][1][1][0]=(dp[z][1][1][1]+dp[z][0][1][0])%M;
	}
	ans%=M;
	//cout<<z<<" "<<ans<<" "<<dp[z][1][0][0]<<h[z]<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dis[1]=1;
	dfs(1);
	ans+=M;
	ans%=M;
	cout<<ans;
	return 0;
}

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