# Insight on TLE in star graphs

Question
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();
}
``````

you are calling solve for evey node, and setting the current node and and its parent unvisited, in star tree case that parent will end looping over all the node

complexity = n *n

1 Like