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). asked 13 Mar, 16:47

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; answered 13 Mar, 16:55
will you (or) anyone explains what is wrong with this code: https://pastebin.com/CBzkhatT
(13 Mar, 17:45)
I think you missed something in the "getEdgeDistances" function... you can find my solution to this problem here https://github.com/Samarth9798/CodechefMarchChallenge2019
(13 Mar, 18:18)

I had 2 TLE / 11 AC with the following:
Now to compute the value of the subtree S rooted at n you can:
answered 13 Mar, 18:54

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 coefficients 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 * x^{r} + st * x^{r+1} + ... + st * x^{r+ct1} + (st+1) * x^{r+ct} + ... + ed * x^{r+(edst+1)*ct1}. Now this can be simplified as : st * x^{r} (1+x+x^{2}+..+x^{ct1}) + (st+1) * x^{r+ct} (1+x+x^{2}+..+x^{ct1}) + ... + ed * x^{r+(edst)*ct} (1+x+x^{2}+..+x^{ct1}) Taking the term (1+x+x^{2}+..+x^{ct1}) common you have as follows : (1+x+x^{2}+..+x^{ct1}) * (st * x^{r} + (st+1) * x^{r+ct} + ... ed * x^{r+(edst)*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+x^{2}+..+x^{ct1}) 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. answered 13 Mar, 21:29
