Did anyone solved this problem using square root tree /compressed super node tree?
1 Like
@gagan86nagpal for speeding up the process you have stated I constructed a super node tree of the tree T2 and for each block I stored a vector of size N which denotes how many edges in this block can be formed from the vertices of the tree T1 if you consider the subtree rooted at each node of the tree T1. Whole complexity seems to be N*sqrt(N) but i was not able to fix the WA and tle in some cases.
I solved it using heavy-light decomposition and BIT.
An edge e1(u1-v1) in T1 and e2(u2-v2) in T2 are interchangeable iff e1 lies on the path between u1-v1 in T2 and e2 lies on the path between u2-v2 in T1.
Let’s number each edge.
If the edges were labeled in such a manner that every path has continuous edge intervals (like edges with edge no l-r form the path between u-v) then we can simply traverse every edge in T2 and add that edge to a continuous interval of edges in T1. Then finally traverse every edge in T1 and update the list of valid edges from T2 for this edge and find the range of values of edges in T2 that would be potential candidates for this edge in T1 (say l-r).
The answer for this edge is the number of valid edges within l-r.
Unfortunately we cannot number the edges such that every path is a continuous set of edges since we would be stuck at branches, however we can choose the longest branch and assign it continuous values so that every path can be expressed as concatenation of lgN paths which are continuous in edge labels.
We can use a BIT to maintain the range updates and queries.
Overall complexity O(Nlg^2N).
I solved it using lca and BIT. I have written a detailed description of my approach here.
For any edge e1(u,v) in T1 there would be a path from u to v having potential candidates. The path again can be decomposed to:
F(u,v) = F(1,u)+F(1,v)_2*F(1,lca)
Now for finding potential candidates on the path from root to a node for any e1, I made the same observation that one endpoint of an edge must belong to the subtree of the one in T1 farther from the root and the other should not.
For this you need edges with the start times of their endpoints incompletely overlapping with the required range [ST(u),EN(u)] due to the above condition.( one will be in this range(subtree property), the other will not).
Denoting ranges as 1,2,3 (< ST(u), between, >EN(u) ) we are interested in (st1,en2)+(st2,en3).
e2 = (st1,en2)+(st2,en2) => ranges ending in region 2 and
s2 = (st2,en2)+(st2,en3) => ranges starting in region 2 .
Hence we want to find s2+e2-2*(st2,en2). Now for computing s2 and e2 you can maintain two bits and update for every start time and end times of the edge.
For computing (s2,e2)=>number of edges lying completely in the subtree of u, for every edge e2(a,b) the common ancestors of (a,b) in T1 should be updated since they are the ones which will be affected if queried for the number of edges e2 lying within their subtree. Also you do not need to go up all the way to the root and just maintain a bit update at the start time of the LCA and for all further ancestors it will automatically be included in your query which is a standard technique.
Finally I am doing all this while performing a dfs on T2 and finding answers for all edges e1 having their endpoint or lca in T2 as the current node in dfs.
Complexity - O(n*Logn)
1 Like
I was able to find some insights. Let’s root both trees at 1. For an edge(a-b (a being closer to root)) in tree t1, traverse the a-b in tree T2.
While traversing , if an edge occur(c-d)s.t. either one among(c,d) occurs in subtree of ‘b’ in T1 while other not. Then increment the answer.
Answer would always be odd.
I was not able to get rid off traversing part which made my algorithm Square complexity.
Please someone put up their observations to complete the solution in desired TL.
Yes, In case of multiple queries this gets speeded up. But in the worst case, it can TL.
I got the HLD trick, it was straightforward but I am having a problem in this
“Then finally traverse every edge in T1 and update the list of valid edges from T2 for this edge and find the range of values of edges in T2 that would be potential candidates for this edge in T1 (say l-r). The answer for this edge is the number of valid edges within l-r”.
Are we assuming here that potential candidates would lie in some range l-r, won’t there exist multiple disjoint ranges? If there exists, then we have to unmark them which could make the complexity N^2(in Worst case) isn’t it ?
there would be just lgN intervals that make up the list of potential candidates, we can query for each in O(lgN) using BIT.
1 Like
Yes, Thanks for your explanation
Keep posting your ideas on your blog , (y)
1 Like