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
Thats a great question. The issue here is subtle, but is a common mistake people make in a lot of tree algorithms.
First of all I assume that adj contains pairs of (node, edge index), since otherwise x is the index of the edge.
Consider a graph where there is a node, $$$u$$$, with $$$n-1$$$ edges in $$$adj[u]$$$. Each edge goes from $$$u$$$ to a node $$$v$$$ which is a leaf. If you call your function for each pair $$$(v,u)$$$ there will be $$$n-1$$$ calls, and in each call you will be iterating over all edges in $$$adj[u]$$$. This means that the time complexity will be $$$O(n^2)$$$ (we ignore constants). Thus in the worst case your algorithm is not $$$O(n)$$$ but $$$O(n^2)$$$, which is too slow for $$$n = 10^5$$$ (which is a typical number of nodes in tree problems).
Instead I would recommend you to try to think about, given edge $$$(u,v)$$$, how many endpoints (ending nodes) can a directed path starting with this edge have. It has to do with subtree sizes.
Let me know if you need more help :)
Thank you for clarification :D, I will try to think about it
Edit : I think i got it, ans(a,b) = n-ans(b,a)
I can just root at 1 and calculate the answer for every edge, and its reverse would be n-answer
Thanks for helping me out :D, Much Appreciated
Exactly :)