Queries on Tree : Course (CodeNCode) (8 Aug 2020 : 2 new centroid decomposition lecture added)

tutorial
, ,
42

in
bool comp(pair<pair<int , int>, pair<pair<int , int> , int> > a, pair<pair<int , int>, pair<pair<int , int> , int> > b) function

you are dividing a.first.first by BLK but not b.first.first , that may be a reason

2 Likes
43

It worked. Thanks very much for the help :blush:

44

you’re welcome buddy

45

How we are deciding the comparator function in the question Tree and Queries?

46

@waqar_ahmad224
First of all…thanks a lot for putting this… excellent work! Really appreciate it.
and …can you please mention…when can we expect videos on centroid decomposition and HLD ? really look out for them.

47

Awesome!
You can also make video on dsu on trees!

48

yes , I will cover that in this series as well.

1 Like
49

19 July 2020 : 1 lecture added
L06 : Introduction to Centroid Decomposition & Related Problems

2 Likes
50

problem L05: GOA On Tree.
i got tle .but i cant find why .Can u please help me?
problem link: SPOJ.com - Problem GOT
my code: 7jcu1j - Online C++0x Compiler & Debugging Tool - Ideone.com

51

8 Aug 2020 : 2 new lectures added for centroid decomposition

L07 : Height and Structure of Centroid Decomposition

L08 : Building Centroid Decomposition Tree (C++ Implementation)

1 Like
52

Brother,also solve some problem about Centroid decomposition and needed HLD lectures from u too… :slight_smile:

53

In this question .
5 5
1 2 3 4 5 → these actual values for nodes.
1 2
1 3
3 4
3 5 → these are indexes of nodes or actual node values?
2 3 4
2 4 3
2 4 5
4 5 1
4 5 3

I am asking because i am confused with your code:
void add(int idx)

{

int node = ft[idx];

nodeF[node]++;

if(nodeF[node] == 1)

{
int c = val[node];

eleF[c]++;

}

else

{

int c = val[node];

eleF[c]–;

}

  1. }
54

Hello , can someone please point out my error in this code for problem D query. I am getting runtime error.

55

This post was flagged by the community and is temporarily hidden.

56

@waqar_ahmad224 Sir , plz make a video on re-rooting technique and related problems.

57

@waqar_ahmad224 I have a doubt in your course queries on trees, you have taught MO’s algorithm using Euler tree flattening. But MO algorithm is also applied on sqrt decomposition for a tree which you have not taught.

So my first question for you is that is the second implementation of MO’s algorithm provides the same time complexity as the Euler Tree gives?

And the second question is that if a problem can be solved using either of the first implementations then is possible to do it with the other implementation?

58

brother in lecture 3 i did everything same as you (completely ditto) but getting a wa on tc 13

59

For this solution of yours on E05 how is Segment tree size 2*N and it is still passing ? Isn’t the segment tree size needs to be 4*N?