洛谷P3994【比赛】Highway 【斜率优化】

题目背景

C国拥有一张四通八达的高速公路网树，其中有n个城市，城市之间由一共n-1条高速公路连接。除了首都1号城市，每个城市都有一家本地的客运公司，可以发车前往全国各地，有若干条高速公路连向其他城市，这是一个树型结构，1号城市（首都）为根。假设有一个人要从i号城市坐车出发前往j号城市，那么他要花费Pi*（i城市到j城市的距离）+Qi元。由于距离首都越远，国家的监管就越松，所以距离首都越远，