Getting tle in using Common segtree in HLD, but not in Different segtree for each heavy path

Блог пользователя shashankagrawal

Автор shashankagrawal, история, 6 лет назад, По-английски

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

heavy light, #segment-trees, #trees

shashankagrawal
6 лет назад
5

Комментарии (5)

Написать комментарий?

jef

6 лет назад, скрыть # |

← Rev. 2 →

+38

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.

→ Ответить

shashankagrawal

6 лет назад, скрыть # ^ |

← Rev. 2 →

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.

→ Ответить