[ZJOI 2018]Line Graph

Difficulty Ratings

Idea Creativity: 5/5
Techniques Used: 3/5
Implementation : 5/5
Very hard problem, a lot of details in implementation too. However, I think that general idea is quite interesting and easy to understand:)

Problem Link

Link in simplified chinese by jiry_2

Simplified Statement

Consider a graph $G$. Create $G'$ as follows:
- each edge in $G$ corresponds to each node in $G'$
- build an edge between two nodes in $G'$ if their corresponding edge in $G$ have a common endpoint
Let $L(G)=G'$. Given a tree $T$ with $N \le 5000$ nodes and $k \le 9$, find the number of nodes in $L^k(T)$ modulo 998244353, where $L^k(G)$ is the function $L$ operated $k$ times on $G$.

Solution

Define $|G|$ as the number of nodes in $G$. Lets see what is $|L^k(G)|$ for small $k$.
$k=1$: Number of edges in $G$.
$k=2$: Number of chains of 3 nodes in $G$.
$k=3$: Number of chains of 4 nodes in $G$ + 3*(Number of stars of 4 nodes in $G$) + 3*(Number of cycles of 3 nodes in $G$) (correct me if wrong)
$k=4$: Some mess...
We realise that each node in $L^k(G)$ corresponds to some connected component of size $\le k+1$, while there might be more than one node corresponding to the same component. As all induced subgraph in $T$ is also a tree, we can formulate $|L^k(G)|$ as follows:
$$\sum_{T_i}^{} w_it_i$$
where $T_i$ are trees that have $\le k+1$ nodes (author says rooted helps implementation), $w_i$ is the number of nodes that represent $T_i$ in $L^k(T)$, and $t_i$ is the number of induced subgraph of $T$ that is equal to $T_i$. So we just have to find $w_i$ and $t_i$.

Finding $w_i$

You just have to compute $|L^k(T_i)|$ and remove nodes in $L^k(T_i)$ that represent only a subset of $T_i$, which can be done by inclusion-exclusion. This part is not the bottleneck of time complexity. The hard part is to compute $|L^k(T_i)|$. You can simulate your way till |$L^{k-4}(T_i)$|, and optain a graph G. You then have to find $L^4(G)$ in $O(no.\,of\,edges\,in\,G)$, which is possible and not too annoying...

Finding $t_i$

You can do this with a very yucky dp... Like some bitmasks and yucky stuff
So then you can find all $w_i$ and $t_i$, and plug into the formula to get the answer.

Comments

Hardest problem i've ever seen...