F. LazerTree
View problem here
Observations:
1. for (u,v), if you root at u, then you can pick at most one node from each subtree of v
2. you can calculate the number of ways to pick for v and u independent and multiply them together
Solution:
You create a generating function = product of (1 + sz[c] * x) for all children c of v, then the number of ways is to choose the coefficient of x^K.
So first you calculate these products in O(NK), then for each query (u,v) and vertex v, you divide the generating function by (1 + sz[c] * x) where c is subtree that u belongs to, and you get answer
Special note, because you can choose v itself as the endpoint, you have to multiply by free choice, which is e's taylor series expansion (1 + x + x^2 / 2 + x^3 / 6 + ... + x^n / n! + ...)
G. Snowstorm
View problem here
We need an persistent data structure that is able to maintain connectivity of the graph online. If it's offline, we can just use DSU, but the problem with DSU is when we do path compression, it destroys the original structure so it's impossible to reverse back to previous states.
The solution to this problem is Kruskal Reconstruction Tree, where you iterate over all the nodes in increasing order. Then for each node, you look at the nodes around you. If they are smaller than you, then you make their parents point to yourself in the reconstruction tree.
The property of this tree is that the LCA of any two nodes in the tree is the smallest strength shovel necessary to get across them. Then we put a CHT LineContainer at each node (since the formula is just a linear equation), and merge the children's linecontainers at each parent. Therefore, for each starting node, we can use binary lifting to find the earliest ancestor that has a thickness <= our strength. You then just do linecontainer query with the weight of the shovel and get the answer 😌
Oh, and also a dp/dijkstra to find the minimum distance to each node with path length i.
Link to Discord discussion about this problem.
H. NumberFactory 2.0
View problem here
HLD decompose into heavy and light children, treat each light children on the heavy path as a leaf node, then you get a chain with a bunch of leaf nods attached to it, so you just need to solve chain case:
Essentially, each operator can be decomposed into (x AND a) XOR b, so each node is (a,b) and you can merge these (a,b) using segment tree.