# Shenyang2019.icpc D Fish Eating Fruit

2019-09-18

ACM

419

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