Question
Submission link
This is from atcoder beginner contest 160 problem F.
This code seems to work under 200 ms for normal graphs but takes over 3 seconds in star graphs. Could anyone provide insight as to why this is happening. I know the euler tour has more length than average, but it takes significantly longer.
Since it’s a bit difficult to read code there, here’s my code on forum.
Code
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
vector<vector<int>> edge;
vector<pair<ll,int>> dp;
const ll p =1e9 + 7;
ll modpower(ll base, ll power, ll mod=p){
ll ans =1;
base%=p;
while(power){
if(power&1){
ans*=base;
ans%=p;
}
base*=base;
base%=p;
power>>=1;
}
return ans;
}
ll fact[200007];
ll invfact[200007];
void computefactorial(){
fact[0]=1;
for(int i=1;i<200007;i++){
fact[i]=i*fact[i-1];
fact[i]%=p;
}
invfact[200006]=modpower(fact[200006],p-2);
for(int i=200005;i>=0;i--){
invfact[i]=(i+1)*invfact[i+1];
invfact[i]%=p;
}
}
vector<int> euler;
vector<bool> vis;
void eulerTree(int u, int &indx)
{
vis[u] = 1;
euler[indx++] = u;
for (auto it : edge[u]) {
if (!vis[it]) {
eulerTree(it, indx);
euler[indx++] = u;
}
}
}
void solve(int u, int v){
if(dp[u].first!=-1){
return;
}
if(u!=v && edge[u].size()==1){
dp[u]=mp(1,1);
return;
}
ll ans=1;
int size=0;
for(int i=0;i<edge[u].size();i++){
if(edge[u][i]==v){
continue;
}
solve(edge[u][i],u);
ans*=dp[edge[u][i]].first;
ans%=p;
ans*=invfact[dp[edge[u][i]].second];
ans%=p;
size+=dp[edge[u][i]].second;
}
ans*=fact[size];
ans%=p;
dp[u]=mp(ans,size+1);
return;
}
ll solve(){
int n;
cin>>n;
edge.resize(n);
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
edge[--u].pb(--v);
edge[v].pb(u);
}
dp.resize(n,mp(-1,0));
vector<ll> ans(n);
solve(0,0);
ans[0]=dp[0].first;
int idx=0;
euler.resize(2*n + 7);
vis.resize(n + 5,0);
eulerTree(0,idx);
for(int i=1;i<idx;i++){
dp[euler[i]]=mp(-1,0);
dp[euler[i-1]]=mp(-1,0);
solve(euler[i],euler[i]);
ans[euler[i]]=dp[euler[i]].first;
}
for(int i=0;i<n;i++){
cout<<ans[i]<<"\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
computefactorial();
solve();
}