Hi,
I was trying to understand the solution of this problem in codeforces. Problem - 771C - Codeforces
Here, I am following these two solution(both are using same technique).
I am not able to understand, what is actually this line do,
inside double for loop,
int rem = (i + j - 2 * depth) % K; //In 1. solution(line 54)
Why we are calculating this rem, and in this way, i+j-2*depth?(what does depth has to do anything and even i and j represent remainder why summing both)?
What is f(u,v). It’s just \lceil dist(u,v)/k \rceil. This can also be written as \frac{dist(u,v ) + c_{u,v}}{k}, where c_{u,v} is the smallest non-negative integer such that k divides dist(u,v) + c_{u,v}. Since we need \sum \frac{dist(u,v ) + c_{u,v}}{k}, we can split this into two parts. \sum dist(u,v ) + \sum c_{u,v}
As we can see, c_{u,v} is only dependent on dist(u,v)\%k.
How do we compute the distance between 2 nodes in a tree?. We can find it by finding the depths of each node, and the depth of it’s LCA(Lowest common ancestor). Let L_{u,v} denote the LCA of u and v.
Then dist(u,v) = depth(u) + depth(v) - 2\times depth(L_{u,v}). This is because it has to go up to its LCA and then come back down. Let’s define dp_{i,j} The number of nodes in the subtree of i at a depth d such that d \equiv j\mod k.
Now let’s choose some node a, and consider \sum_{L_{u,v}=a} c_{u,v}. This is the sum of c over all pairs of nodes whose LCA is a. Since all pairs of nodes have some LCA, this includes all of them.
We can see that the LCA of two nodes will be a only of the two nodes lie in different subtrees of a. The two for loops are counting the number of pairs of each \mod k
At each point count_subtree[a][i](dp_{a,i}) stores the number of nodes at a depth of i \mod k from the subtrees already accounted for. So for each subtree, we are calculating the number of pairs of nodes at depth i,j \mod k. That is all the information needed to find c.
Therefore i + j - 2\times depth gives us the distance \mod k. Using this information we can compute needed(c), and multiply it by the number of pairs.
Thankyou @everule1. Really appreciated the explanation. Also, this technique of multiplying for curent parent array to child array is new for me, and I require one more help on this. Lately, I am doing some dp problems on Tree and I also came across similar problem.
Problem - D - Codeforces.
I am following this solution [Codeforces 161D – Distance in Tree : Solution – T00 PR0] here, the approach used is little bit different. I was wondering can this be done using the above* technique? In otherwords, for each “a”(node), I will do dfs for each of its child(just like above*) and then(which will give array where dist[b][i]=no. of nodes at distance i in subtree rooted at “b”. Then after this how should I proceed? Eventually, I need is multipilcation of no. of nodes in each of subtree at distance x and k-x(in all other subtree). Like can this be done in above* technique where parent array is used for multipilcation not as leftover but storing the mid result as we are doing above*. (above* meaning = 771C solution)
Yes, of course it’s possible.
dp[i][j] is the number of nodes at a depth of j with respect to i.
dfs(u) returns the number of pairs contained in the subtree of u with distance k.
Thankyou very much.