Help in the centroid decomposition problem

help
1

Hi all!

I am solving some problems mentioned in this blog : link

but I am stuck in the problem

I tried the idea the same as in this problem: link but used set for storing the minimum.

my sol: = link

Any help will be appreciated.

2

Try using multiset bro, I didn’t actually go through your code, but suspect using set might be one of the issues because their might be multiples nodes with the same distance, and set will be storing that distance just once.

For example, say we have two nodes x and y at distance d from node u.

Set of u : {d}

If you flip the color of x, you remove d, Set of u = empty.
But it should still be {d}.

1 Like
3

Thanks for replying
I solved with set of pairs #include<bits/stdc++.h>#include <ext/pb_ds/tree_policy.hpp>#include <ext/pb_ - Pastebin.com
The reason it works because (d,v) guaranteed to be unique
Although multiset would be more elegant i guess