Given a tree of $$$n$$$ nodes, I need to find for every directed edge $$$(a,b)$$$ in it the number of paths in the tree that start with this directed edge
This was a subproblem I faced in two recent contests (YAC3 B, Codecraft22 F)
I wrote a recursive DP solution to it in $$$O(2*edges)$$$ which is $$$O(2n-2)$$$, but it got TLE in both problems and so far I don't know why
Here is my code :
int n,ans=0,k;
vector<pair<int,int>>adj[INF],u;
vector<int>dp(SZ,-1);
int slv(int e)
{
if(dp[e]!=-1){return dp[e];}
int c=1,nd=u[e].second,pr=u[e].first;
for(int i=0;i<adj[nd].size();i++)
{
int x=adj[nd][i].first;
if(x==pr){continue;}
c+=slv(adj[nd][i].second);
}
return dp[e]=c;
}
/// n --> size of the node
/// adj[i] --> the adjacency list, for node i it carries a vector of pairs for each edge of node i : (the index of an edge, the node connected to node i by this edge)
/// dp[x] --> the answer for the required problem above for an edge of index x
I suspect this could be due to using recursion, is there a way to optimize calculating the answer for this subproblem? It has been haunting me for days :(
Here are my submissions if you are wondering how I got TLE:
YAC3 B
Codecraft22 F
I doubt it is in a subproblem other than this one