P2305[NOI2014]购票Solution记\(f_{i}\)表示\(i\)节点处的答案。\(f_1=0\)。记\(d_i\)表示根节点到点\(i\)的距离，容易得到\(O(n^2)\)的dp转移：\[f_{i}\xleftarrow{\min}f_j+(d_i-d_j)\timesp_i+q_i,d_i-d_j\lel_i\]设\(y=f_i-d_i\timesp_

P2305[NOI2014]购票题意今年夏天，NOI在SZ市迎来了她三十周岁的生日。来自全国\(n\)个城市的OIer们都会从各地出发，到SZ市参加这次盛会。全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的\(n\)个城市用\(1\simn\)

题意给定一棵边带权且以\(1\)为根的树，从后代结点\(u\)跳到祖先结点\(v\)的代价为\(dp_u+q_u\)，其中\(p_u,q_u\)是给定的常数，\(d\)是\(u,v\)的树上距离。要

P2305[NOI2014]购票设\(f_{x}\)表示从\(x\)点跳到\(1\)的最少费用。考虑\(x\)的一个祖先\(u\)，有\[f_x=f_{u}+\text{dis}_{u,x}\timesp_x+q_x\]其中需要满足