Yahia_Emara's blog

Help with a tree standard problem
By Yahia_Emara, 2 years ago, In English

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

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply