Shenyang2019.icpc D Fish Eating Fruit

The Question

Fish eating fruit on jisuanke

Given an undirected acyclic graph G, all possible path P in the graph, calculate:

$$ \begin{align*} N(Durian) & = (\sum_{p \in P_{Dur}} |p|) \% (1e9+7), \text{where } P_{Dur} = \{p | p \in P, |p| \% 3 = 0\} \\ N(Papaya) & = (\sum_{p \in P_{Pap}} |p|) \% (1e9+7), \text{where } P_{Pap} = \{p | p \in P, |p| \% 3 = 1\} \\ N(Avocado) & = (\sum_{p \in P_{Avo}} |p|) \% (1e9+7), \text{where } P_{Avo} = \{p | p \in P, |p| \% 3 = 2\} \\ \end{align*} $$

The first taste

In the contest, a handsome foriegn teammate conviced me that this problem can be solve using LCA. I tried. And it did work, with the help of dijkstra.

My solution is to, first of all, run dijkstra, and get the distance between root node and every other nodes. Then, calculate the LCA for every two nodes. The desired result is:

$$ \begin{align*} & V: \text{The nodes set in the graph G} &\\ & R: \text{The root node} &\\ & A, B: \text{Any two nodes (including the root node)} &\\ & C = LCA(A, B): \text{The least common ancestor for A and B} &\\ & &\\ & Dist(A, B) = |RA| + |RB| - |RC| &\\ & D_i = \{ Dist(A, B) | A, B \in V, Dist(A, B) \% 3 = i \}, i \in {0, 1, 2} &\\ & &\\ & Res_i = \sum_{d \in D_i} d \% (1e9+7), i \in {0, 1, 2} &\\ \end{align*} $$

It worked, but we got TLE for looping though all the nodes, which is \( O(n^2 log n) \).

The second trial

After the contest, I was told that this is a DP problem. You calculate the times an edge is accessed, times it with the weight, sum them up by the modulus of 3, you got the result.

$$ \begin{align*} & V: \text{The nodes set in the graph G, where node -1 does not exist} &\\ & E_u: \text{The edges set of node u, } E_{-1} = \varnothing &\\ & w_e: \text{The weight of edge e} &\\ & v_e: \text{The other end of edge e (of node u)} &\\ & &\\ & E_{fa, u} = \{ e | e \in E_u, e \notin E_{fa} \} &\\ & DP_i(fa, u) = \sum_{e \in E_{fa, u}}( DP_j(u, v_e) + w_e * CNT_j(u, v_e) + w_e * \lfloor e^{-j} \rfloor ), \text{where } i \in \{0, 1, 2\}, j = (3 + i - w_e\%3) \% 3 &\\ & CNT_i(fa, u) = \sum_{e \in E_{fa, u}}( CNT_j(u, v_e) ) + 1, \text{where } i \in \{0, 1, 2\}, j = (3 + i - w_e\%3) \% 3 &\\ & &\\ & Res_i = \sum_{u \in V} DP_i(-1, u), i \in \{0, 1, 2\} &\\ \end{align*} $$

This one, however, also got TLE. Oh, FISH!

The final solution

The reason why the second solution still can be improved is that there is repeated calculation. We know that the distance of node A to node B is equal to the distance of B to A, so calculation can be saved here.

With that in mind, I had to re-design the whole algorithm. When using DFS to solve the problem, the second solution only records the information in one way, which is from children nodes to the father node. So, it is clear that if the algorithm also passes down information from the father node to its children nodes, the problem mentioned in the second trial can be settled.

$$ \begin{align*} & V: \text{The nodes set in the graph G, indexing from 0. Node -1 does not exist} &\\ & E_u: \text{The edges set of node u}, E_{-1} = \varnothing &\\ & e_{u, v}: \text{The edge from u to v} &\\ & w_e: \text{The weight of edge e} &\\ & u_e: \text{The starting node of edge e (from node u to v)} &\\ & v_e: \text{The ending node of edge e (from node u to v)} &\\ & Ord_u(e): \text{The order of edge e in } E_u, Ord_u(-1) = \infty &\\ & fa(u | a): \text{The father node of node u when performing DFS from node a}, fa(a | a) = -1 &\\ & &\\ & \tilde{e}_{u, v} = e_{v, u} &\\ & E_{u | a} = \{ e | e \in E_u, \tilde{e} \notin E_{fa(u | a)} \} &\\ & EP_u(k) = \{ e | e \in E_u, Ord_u(e) < Ord_u(k) \} &\\ & DP_i(u, k | a) = \sum_{e \in E_{u | a} \cap EP_u(k)}( DP_j(v_e, -1 | a) + w_e * CNT_j(v_e, -1 | a) + w_e * \lfloor e^{-j} \rfloor ), \text{where } i \in \{0, 1, 2\}, j = (3 + i - w_e\%3) \% 3 &\\ & CNT_i(u, k | a) = \sum_{e \in E_{u | a} \cap EP_u(k)} CNT_j(v_e, -1 | a) + 1, \text{where } i \in \{0, 1, 2\}, j = (3 + i - w_e\%3) \% 3 &\\ & &\\ & DPF_i(u | a) = DP_j(fa, e_{fa, u} | a) + DPF_j(fa | a) + w_e * CNTF_i(u | a), \text{where } j = (3 + i - w_e\%3) \% 3, fa = fa(u | a) &\\ & CNTF_i(u | a) = CNTF_j(fa | a) + CNT_j(u, e_{fa, u} | a), \text{where } j = (3 + i - w_e\%3) \% 3, fa = fa(u | a) &\\ & &\\ & Res_i = 2 * \sum_{u \in V}( DP_i(u, -1 | 0) + DPF_i(u | 0) ), \text{where } i \in \{0, 1, 2\} &\\ \end{align*} $$

For \( DP_i \) and \( CNT_i \), they are basically the same as the second solution, which calculate the distances between every node and its children. But \( DPF_i \) and \( CNTF_i \) are added to calculate the distances between every node and the nodes in other branches of its ancestors that already encountered while performing DFS.

There are still two kinds of distances that are not taken into account. One is the distances between a node and its ancestors, and the other is the distances between a node and the nodes in other branches of its ancestors that haven't visited while performing DFS. They are equal to \( DP_i \) and \( DPF_i \) respectively. So doubling the sum will be the result.