shashankagrawal's blog

Getting tle in using Common segtree in HLD, but not in Different segtree for each heavy path
By shashankagrawal, history, 5 years ago, In English

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

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

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

Your HLD looks wrong. You have

if(adj[v][0] != p && tot[u] > tot[adj[v][0]]) {
	swap(u, adj[v][0]);
}

and later

up[u] = (u == adj[v][0] ? up[v] : u);

So if the adj[v][0] = p for every node, the complexity blows up. Adding the following code fixes it:

if(adj[v].size() >= 2u && adj[v][0] == p) {
	swap(adj[v][0], adj[v][1]);
}

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 in dfs_tot looks like is supposed to be the size of the subtree, but then you do tot = cr; which makes no sense.

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

    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.

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

    Thank you very much, I used what you told and it worked.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ignore my above comment understand the mistake now. Again thank you!!!

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shashankagrawal (previous revision, new revision, compare).

→ Reply