Submission #634237

#	Time	Username	Problem	Language	Result	Execution time	Memory
634237		Mahdi	Subtree (INOI20_subtree)	C++17	100 / 100	163 ms	22820 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e5+5, M=1e9+7;
int n, m, dis[N], up[N], dn[N], dp[N], pd[N], a[N], b[N], c[N];
vector<int>g[N], kd[N];
bool mk[N];
pii be[N];

inline int tav(int x, int y){
    int res=1;
    while(y){
        if(y&1)
            res=1LL*res*x%M;
        x=1LL*x*x%M;
        y>>=1;
    }
    return res;
}

inline int rev(const int &x){
    return tav(x, M-2);
}

void dfs(const int &v, const int &p){
    mk[v]=1;
    be[v]={-1, -1};
    for(int u: g[v]){
        if(!mk[u]){
            dis[u]=dis[v]+1;
            kd[v].push_back(u);
            dfs(u, v);
            if(be[u].S!=-1 && up[be[u].S]!=u)
                be[v]={u, be[u].S};
        }
        else if(u!=p){
            if(dis[u]>dis[v])
                dn[v]=u;
            else
                up[v]=u;
        }
    }
    if(up[v]!=-1)
        be[p]={v, v};
}

void dfs(const int &v){
    for(int u: kd[v])
        dfs(u);
    if(dn[v]==-1){
        ll A=0, B=1;
        for(int u: kd[v]){
            A+=dp[u];
            B=B*(pd[u]+1)%M;
        }
        A+=B;
        dp[v]=A%M;
        pd[v]=B;
        if(be[v].S!=-1){
            int u=be[v].F;
            ll bc=1LL*pd[v]*rev(pd[u]+1)%M;
            a[v]=bc*(a[u]+1)%M;
            a[v]+=c[u];
            if(a[v]>=M)
                a[v]-=M;
            b[v]=b[u]*bc%M;
            c[v]=c[u]+b[v];
            if(c[v]>=M)
                c[v]-=M;
        }
        else if(up[v]!=-1){
            a[v]=0;
            c[v]=pd[v];
            b[v]=pd[v];
        }
    }
    else{
        ll A=0, B=1;
        for(int u: kd[v]){
            A+=dp[u];
            if(u!=be[v].F)
                B=B*(pd[u]+1)%M;
            else
                B=B*(a[u]+1)%M;
        }
        A+=B;
        pd[v]=B;
        dp[v]=A%M;
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int u, v;
        cin>>u>>v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }   
    memset(up, -1, sizeof(up));
    memset(dn, -1, sizeof(dn));
    dfs(0, -1);
    dfs(0);
    cout<<dp[0]<<'\n';
}

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