NKOJ 3254 ZJOI 2015 点分治《幻想乡战略游戏》 NKOJ 3254 ZJOI 2015 点分治《幻想乡战略游戏》

P3254【ZJOI2015 Day1】幻想乡战略游戏

问题描述

傲娇少女幽香正在参与一个极具战略性的游戏。
然而现在的网游厂商却不断增大地图规模。
由于地图过大导致幽香难以观察全局。
更不用说与其他玩家交战了。
整个游戏世界构成一个树状结构。
这里共有n块空地通过n-1条带权边连接起来。

在游戏中：
假设在点u设置了一个补给站，则位于v点的军队数量为dv。

而每天维护这些军队所需的费用则为dv乘以u到v的距离。

总计每天的费用总额则由所有军地点所需费用之和决定。

其中dist(u,v)表示u到v在树上的距离（唯一路径的权和）。
因此，在游戏中规定了这样的限制：幽香必须为游戏设定一个固定补给站点位置。

在游戏运行过程中：
幽香可能会增派军队至某些关键地段；
也会考虑从某些空地上撤回军队数量；
与此同时，
为了节省资源，
幽香通常会根据情况调整补给站点位置来节省开销。

你是否可以帮助她完成这一安排呢？

输入格式

第一行两个数n和Q分别表示树中的节点数目以及幽香操作的总次数。
接下来的n-1行中，每一行给出