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: 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: It worked, but we got TLE for looping though all the nodes, which is . 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. This one, however, also got TLE. Oh, FISH! The final solution The reason why the second solution still can