Submission #796935

#	Time	Username	Problem	Language	Result	Execution time	Memory
796935		ashcomp	Subtree (INOI20_subtree)	C++14	100 / 100	86 ms	33264 KiB

Main

#include<bits/stdc++.h>

using namespace std;
 
#define all(x) x.begin() , x.end()
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pb push_back
#define qb pop_back
#define F first
#define S second
#define wall cerr<<"--------------------------------------"<<endl
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef double db;

const ll INF = 1e9;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

ll n , m , h[maxn] , dp[maxn] , p[maxn] , par[maxn] , other[maxn];
bool tp[maxn] , mark[maxn];
vector<ll> g[maxn] , ar[maxn] , sum[maxn] , pre[maxn] , suf[maxn];

void dfs0(ll v)
{
        //cout<<v<<" ";
        mark[v] = 1;
        for(auto u : g[v]){
                if(u==p[v])continue;
                if(mark[u]==1 && h[v]>h[u]){
                        par[v] = u;
                        tp[u] = true; 
                        continue;
                }
                if(mark[u]==1)continue;
                p[u] = v;
                h[u] = h[v] + 1;
                dfs0(u);
                if(par[v]==-1)par[v] = par[u];
                if(par[v]==v)par[v] = -1;
        }
        //cout<<v<<" ";
}

void dfs1(ll v)
{
        mark[v] = 1;
        dp[v] = 1;
        other[v] = 1;
        for(auto u : g[v]){
                if(u==p[v] || mark[u]==1){
                        continue;
                }
                dfs1(u);
                if(par[u]==-1 || (par[u]!=par[v] && par[u]!=v)){
                        //cout<<v<<" , "<<u<<"\n";
                        other[v] = (other[v] *(dp[u]+1))%mod;
                }
                dp[v] = (dp[v] * (dp[u]+1))%mod;
        }
        if(par[v]!=-1){
                ar[par[v]].push_back(other[v]);
        }
        if(tp[v]==1){
                dp[v] = 0;
                ar[v].push_back(other[v]);
                /**/
                ll sz = ar[v].size();
                for(int i=1; i<=sz; i++){
                        suf[v].push_back(0);
                        pre[v].push_back(0);
                        sum[v].push_back(1);
                }
                suf[v][sz-1]=ar[v][sz-1];
                for(int i=sz-2; i>=0; i--){
                        suf[v][i] = (suf[v][i+1]*ar[v][i])%mod;
                }
                pre[v][0] = ar[v][0];
                for(int i=1; i<sz; i++){
                        pre[v][i] = (pre[v][i-1]*ar[v][i])%mod;
                }
                sum[v][0]=1;
                for(int i=1; i<sz; i++){
                        sum[v][i] = (sum[v][i-1]+pre[v][i-1])%mod;
                }
                for(int i=0; i<sz-1; i++){
                        dp[v] = (dp[v] + (sum[v][i]*suf[v][i+1])%mod)%mod;
                }
        }
}

int main()
{
        ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
        cin>>n>>m;
        for(int i=1; i<=m; i++){
                int v,u; cin>>v>>u;
                g[v].push_back(u);
                g[u].push_back(v);
        }
        for(int i=1; i<=n; i++){
                p[i] = -1;
                par[i] = -1;
        }
        dfs0(1);//cout<<"\n";
        for(int i=1; i<=n; i++){
                mark[i] = 0;
        }
        dfs1(1);//cout<<"\n";
        // for(int i=1; i<=n; i++){
        //         cout<<i<<" : "<<dp[i]<<"\n";
        // }
        ll ans = 0;
        for(int i=1; i<=n; i++){
                ans = (ans + dp[i])%mod;
        }
        cout<<ans;
        return 0;
}
/*
10 10
1 2
2 3
3 4
4 5
5 6
4 7
3 8
2 9
1 10
1 5
*/
/*
5 4
1 2
1 3
2 4
2 5

ans = 17;
*/
/*
8 9
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4
7 8

ans = 52;
*/
/*
by
          _____                    _____                    _____                    _____                  
         /\    \                  /\    \                  /\    \                  /\    \                 
        /::\    \                /::\    \                /::\____\                /::\    \                
       /::::\    \              /::::\    \              /:::/    /                \:::\    \               
      /::::::\    \            /::::::\    \            /:::/    /                  \:::\    \              
     /:::/\:::\    \          /:::/\:::\    \          /:::/    /                    \:::\    \             
    /:::/__\:::\    \        /:::/__\:::\    \        /:::/____/                      \:::\    \            
   /::::\   \:::\    \       \:::\   \:::\    \      /::::\    \                      /::::\    \           
  /::::::\   \:::\    \    ___\:::\   \:::\    \    /::::::\    \   _____    ____    /::::::\    \          
 /:::/\:::\   \:::\    \  /\   \:::\   \:::\    \  /:::/\:::\    \ /\    \  /\   \  /:::/\:::\    \         
/:::/  \:::\   \:::\____\/::\   \:::\   \:::\____\/:::/  \:::\    /::\____\/::\   \/:::/  \:::\____\        
\::/    \:::\  /:::/    /\:::\   \:::\   \::/    /\::/    \:::\  /:::/    /\:::\  /:::/    \::/    /        
 \/____/ \:::\/:::/    /  \:::\   \:::\   \/____/  \/____/ \:::\/:::/    /  \:::\/:::/    / \/____/         
          \::::::/    /    \:::\   \:::\    \               \::::::/    /    \::::::/    /                  
           \::::/    /      \:::\   \:::\____\               \::::/    /      \::::/____/                   
           /:::/    /        \:::\  /:::/    /               /:::/    /        \:::\    \                   
          /:::/    /          \:::\/:::/    /               /:::/    /          \:::\    \                  
         /:::/    /            \::::::/    /               /:::/    /            \:::\    \                 
        /:::/    /              \::::/    /               /:::/    /              \:::\____\                
        \::/    /                \::/    /                \::/    /                \::/    /                
         \/____/                  \/____/                  \/____/                  \/____/                 
                                                                                                            
*/
//NOGHRE SHODANAM BAD NIST :_)

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