CF2176D

能想到的点：

• 最短的斐波那契路径是任意一条边。
• 所以可以以边为状态进行 DP
• 令 $dp_{u, v}$ 为从 $u, v$ 这条边开始的斐波那契路径的数量。
• $dp_{u, v}=dp_{u, v} + dp_{v, w} (a_{w}=a_{u}+a_{v})$

那么可以知道 $dp_{u,v}$ 是由 $dp_{v,w}$ 转移过来的，所以应该先处理 $dp_{v,w}$，根据性质可以知道，$v,w$ 边的边权和严格大于 $u,v$。

所以可以按照边权和进行从大到小的转移，对于边权相等的两条边，顺序前后不互相影响，因为它们之间不可能相互转移。

但是如何判断 $(a_{w}=a_{u}+a_{v})$ 呢？爆搜的复杂度太高了，$M^2$ 一定会超时，不妨改变一下状态。

状态之间能否进行转移，只与 $u,v,w$ 点权有关，所以可以考虑用 $v$ 的点权代替，由于点权范围很大，需要用到 map。

$dp_{u,cost_{v}}$ 代表从 $u$ 开始，走到点权为 $cost_v$ 的点，以这些边为起始边的斐波那契路径的数量。

对于从同一个点出发、边权相同的两个边，它们在 DP 计算后续状态的作用完全是相同的，所以可以这样进行压缩。

转移方程：

$dp_{u,cost_{v}}=dp_{u,cost_{v}}+dp_{v,cost_{w}}+1$

$cost_{w}=cost_{u}+cost_{v}$

加一代表 $u,v$ 这条边代表的斐波那契路径。

答案如何统计呢？

计算完后统计每个点的答案即可，也可以边计算边把增量累加到答案上，这样可以保证每个点的贡献只被计算一次。