PTREE - Discussion

general
,
1

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).

2

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[u] ] + 1;

3

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
4

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.

5

will you (or) anyone explains what is wrong with this code: #include <iostream>#include <vector>#include <algorithm>#include <cassert> - Pastebin.com

6

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

you can find my solution to this problem here