PTREE - Discussion

Share your approach for getting PA or AC for the PTREE problem, I tried to use simple DFS on it (for PA) but failed…The Editorials will probably take some time, so please share your approaches(for PA or Complete AC).

use disjoint sets to store the root of every node…

For example:
if n = 6
for tree with edges
1 2,
1 3,
2 4,
2 5,
4 6

then the disjoint set will be like:
1 1 1 2 2 4

from here u can easily calculate the distance like:

distance[ u ] = distance[ root ] + 1;

I had 2 TLE / 11 AC with the following:

  1. Re-labeling the graph so that nodes a and b of the same depth are |a-b| nodes apart. Given a and b at the same layer this can efficiently give you a’ and b’ in the next layer such that [a’, b’] is the set of children of nodes in [a, b].

  2. For each node u, precomputing its deepest descendant v (and it’s depth D(u)) such that every node that is an ancestor of v and not u has exactly one child.

  3. Precomputing an RMQ data structure to answer min(D(i)) for a <= i <= b (could be done in O(1)). Given [a, b] at the same layer this could efficiently give you the nearest layer of [a, b]'s descendants N([a, b]) = [c, d] with |c-d| > |a-b|.

Now to compute the value of the subtree S rooted at n you can:

  1. Start with the interval I=[n, n]
  2. Use the nodes in I and it’s descendants preceding N(I) to compute part of the value (could be done in O(1))
  3. I = N(I)
  4. Repeat 2 or return the total value when done

The solution I did was based on some observations. Initially if there is 1 node at depth 1,x1 nodes at depth 2,x2 nodes at depth 3,… .

First observation is that you must assign higher co-efficients to higher depths

Now the second observation is as follows : x1<=x2<=x3<=…<=xd . It is because of the perfect tree property.

Third observation is if xi=xi+1=…=xj , put them in a group together. The maximum number of such groups <= 633. This is because in worst case all xi are strictly greater than previous by 1 which gives us 1+2+3+…x = 2e5, which gives max value of x as 633.

Now if a group starts at depth st and ends at depth ed, with each depth having some ct nodes and there have been total of r nodes before depth st, then the value for the group is as follows :

st * xr + st * xr+1 + … + st * xr+ct-1 + (st+1) * xr+ct + … + ed * xr+(ed-st+1)*ct-1.

Now this can be simplified as :

st * xr (1+x+x2+…+xct-1) + (st+1) * xr+ct (1+x+x2+…+xct-1) + … + ed * xr+(ed-st)*ct (1+x+x2+…+xct-1)

Taking the term (1+x+x2+…+xct-1) common you have as follows :

(1+x+x2+…+xct-1) * (st * xr + (st+1) * xr+ct + … ed * xr+(ed-st)*ct).

The first term is a GP and the second is an AGP.

Now this can be simplified using some math formulas and calculations, like noticing that the term (1+x+x2+…+xct-1) gets cancelled out with one of the denominators of DP and avoiding inverse by taking denominator separately at the end for all terms thus having only a single inverse call and memoizing power function calls for each query I made this solution pass.

will you (or) anyone explains what is wrong with this code: https://pastebin.com/CBzkhatT

I think you missed something in the “getEdgeDistances” function…

you can find my solution to this problem here