Can any one help me with why this solution is getting TLE, are the constants too high? My solution is here in which I made single segment tree for whole of the tree And the one which got AC, in which I made different segtree for each heavy path, is here
Edit :- Got it now, Thanks to jef
Your HLD looks wrong. You have
and later
So if the
adj[v][0] = p
for every node, the complexity blows up. Adding the following code fixes it:You implemented it slightly differently in the other submission, so it doesn't have the same problem, but it still looks a bit wrong. The
tot
variable indfs_tot
looks like is supposed to be the size of the subtree, but then you dotot = cr;
which makes no sense.But I have also done ~~~~~ if(u == p) continue; ~~~~~
So, If any node has atleast 1 child and
adj[v][0] = p
, then it will surely be swapped with adj[v][1], and then loop continues, and hence adj[v][0] will never be p except for leaves. So, Can you please elaborate more?And Sorry for the confusion, But in the second submission I used a different idea for forming the heavy paths, which is I am using length of heavy path down the node instead of subtree size of that node.
Thank you very much, I used what you told and it worked.
Ignore my above comment understand the mistake now. Again thank you!!!
Auto comment: topic has been updated by shashankagrawal (previous revision, new revision, compare).