The editorial of ARC171C mentions that the sum of $$$\prod deg(u)!$$$ over all spanning subgraphs can be computed using DP but doesn't mention how. So I created a blog post that discusses how to compute:
- Number of spanning subgraphs where root vertex has degree $$$d$$$.
- Sum of $$$\prod deg(u)!$$$ over all spanning subgraphs
- Sum of $$$\sum deg(u)$$$ over all spanning subgraphs
To help you solidify the concepts discussed, I've created 2 + 1 practice problems. You can access them here: https://codeforces.me/group/7Dn3ObOpau/contest/503270
https://cfstep.com/training/tutorials/trees/dp-on-spanning-subgraphs-of-a-tree/
The problems are untested. If you see any issues, please let me know.
Thanks!
Hi, for the probelm, Sum of degrees of each subgraph, I am not able to solve it. This is how I thought of it —
Extension Phase — We won't be adding the edge between u and c. So, the answer will be the sum of the terms on both the sides. So, ndp[d] = dp[src][d]+dp[child][now]
Correction Phase — We will add an edge between u and c. Due to adding an edge, the degree of nodes present in both u's and c's side will increase by 1. So, total degree increase will be 2. Hence, ndp[d+1] = dp[src][d]+dp[child][now]+2.
However, this doesn't match the sample test case answers. Where am I going wrong ? Can you share your solution ?
The correction needs to be applied to all the subgraphs that are going to be created, not just one. It is true that adding an edge between parent and child will increase both their degrees by 1. However, there can be multiple ways to create a configuration where parent has degree $$$d$$$, and child has degree $$$now$$$. Remember that your DP table stores the sum of scores of all such configurations.
Suppose there are $$$L$$$ valid subgraphs for parent, and $$$R$$$ valid subgraphs for child. Also, let's call $$$lsum = dp[src][d]$$$ and $$$rsum = dp[child][now]$$$. Then, combining these subgraphs would result in
Therefore, you also need to maintain the count DP from the first problem to quickly compute $$$L$$$ and $$$R$$$.
I'm intentionally leaving out the details on how these equations were arrived at. Let me know if something is not clear. You can find my code here
Very helpful. Thanks ! Just AC'd the problem.
The tutorial shows you how to derive the equation when combining subgraphs, by assuming $$$P_1 + P_2 + P_3$$$ on the parent's side and $$$P_4 + P_5$$$ on the child's side.
Similarly, you can assume $$$S_1 + S_2 + S_3$$$ on the parent's side and $$$S_4 + S_5$$$ on the child's side for this problem. If you decide to leave the edge, then the valid configurations are:
If you sum them up, you get
Similarly, you can derive for the case when the edge is present.
Thanks a lot!
Just derived for the case when the edge is present. Assuming S1+S2+S3 on the parent's side and S4+S5 on the child's side, the valid configurations will be:
Which is equal to —
= 2*(S1+1)+2*(S2+1)+2*(S3+1)+3*(S4+1)+3*(S5+1)
= 2*(S1+S2+S3)+ 2*(1+1+1) + 3*(S4+S5) + 3*(1+1)
= 2*(S1+S2+S3)+ 2*(No subgraphs from parents' side) +3*(S4+S5)+3*(No of Subgraphs from child's side)
So, Generalizing the equation, we get —
= R*(Lsum)+R*L+L*(RSum)+L*R
= R*(Lsum+L)+L*(Rsum+R)
Hi, In the Induced subgraphs with degrees 0, 1, and >= 2 section, you are taking degrees of parent and child to be {0,1,2}. Won't you miss some of the cases ?
Like if the parent can have degrees {0,1,2,3,4,5,6} and the child can have degrees {0,1,2,3,4}. Currently you are taking only {0,1,2} from the parent and {0,1,2} from the child. What about those cases when following degrees are taken from the parent and child respectively — {3,0},{3,1}...{3,4},{4,0},{4,1},{4,2}...{4,4}....similarly upto {6,4} ? Aren't you missing those cases as these pairs too would contribute to >=2 ?
$$$dp[u][2]$$$ doesn't mean the number of configurations where node $$$u$$$ has degree $$$2$$$. It is the number of configurations where the degree of this node is any number $$$\geq 2$$$. Is the degree 3? 5? 10? you don't know, but you do know that the sum of all possible ways to create degree $$$\geq 2$$$ is residing inside $$$dp[u][2]$$$.
So, when you combine the parent $$$dp[u][2]$$$ with child $$$dp[child][1]$$$, you are merging all the subgraphs of the parent where degree is $$$\geq 2$$$, but the child's degree is exactly equal to $$$1$$$. What can you say about the resulting subgraph if you keep the edge leading to the child? It will have degree $$$> 2$$$, hence, you can again store it in $$$ndp[2]$$$.
So in your example, the partition for parent is
Similarly, the partition for child is
I am not able to fully comprehend this. In the above code, "d" was being iterated in the range [0,adj[u].size()) and "now" was being iterated in the range [0,adj[c].size()). Now, you are iterating only {0,1,2} for both parent and child. So, how are you able to store all the states dp[u][>=2] without even iterating over those possibilities ?
Now, what happens when node $$$c$$$ enters? The resulting degree can also be $$$3$$$. But, we do not have a slot to store degree 3. But, the last slot stores the answer for all degrees $$$\geq 2$$$, not just 2. So, we can increment the last slot, making the DP value $$$[1, 3, 4]$$$. What does $$$4$$$ in the last slot indicate? It should be equal to number of ways to create degree 2 + number of ways to create degree 3. That's why it is set to $$$3 + 1 = 4$$$.
Node $$$d$$$ enters. DP values would become $$$[1, 4, 11]$$$. Can you see how we were able to merge the degree $$$3$$$ case of node $$$u$$$ and the degree $$$1$$$ case of node $$$d$$$ to produce a degree $$$4$$$ case without even iterating over it? There are $$$dp[u][2]$$$ ways to achieve all configurations where degree is $$$\geq 2$$$. So even if we don't know how many configurations of exactly each degree exist, we can still get the new configuration if we know the summation of all of them.
Keep in mind that you are not iterating over the degrees in the for loop. The for loop is just a way to combine the subgraphs of both the parts. You are trying to compare it to fixed-degree code, that is why you are getting confused. And even if you try to compare, you forgot one important part of the comparison: Yes, we are iterating over {0, 1, 2} only instead of $$$adj[u].size$$$, but also notice that we are incrementing the same DP state of $$$2$$$ multiple times. We did not do this before.
Try to incrementally add nodes $$$e$$$, $$$f$$$, $$$g$$$, etc, and compute the DP array on paper to understand how it works.
Yeah, I just drew the dp table for both the cases when d and now were iterated over the number of their children and when they were iterated over {0,1,2}. dp[u][2] in the latter case indeed stores the sum dp[u][2]+dp[u][3]+...dp[u][n-1] of the former case.
It all makes sense now. Thanks a lot !