题解与讨论区 1180: 东来紫气满函关

题解与讨论区 1180: 东来紫气满函关

[命题人 : ]
时间限制 : 4.000 sec  内存限制 : 256 MB

返回问题页面

题目描述

李将军最近还有一个麻烦事,正好碰到了善于计算的叶书生。

函谷关是通往长安的重要旅游景点。

在李将军等名将的领导下,太平无忧,昔日的要塞已经变成了前往长安路上的必游之地。

为了淡化函谷关的军事感,新任工部侍郎欧阳微(字晓栋)决定将函谷关的道路染成紫色,在长安东侧,以取“紫气东来”之祥瑞。

函谷关道路系统可以看作一个树,规定根节点为停车场所在地,在停车场我们有若干台牛车。

每台牛车均从停车场出发,开到节点v(该过程无需花费),然后付出ci的花费把结点vw的道路染成紫色,该过程不重复经过同意节点。(可以理解为对于所有的vw,都有vw的祖先。)

虽然大唐很有钱,但是玄宗不愿浪费人民的劳动成果,他责令欧阳尚书选出花费最少的方案,使得所有的道路都被染成紫色。

欧阳尚书对李将军说“你曾经也是驻守在这里的一名伍长,看你对这里有很深的感情,这个难题就交给你了”。

谁不知道欧阳尚书就是超级计算机的管理员啊!李将军无奈,找到了叶书生。

叶书生说“其实我可以随时和超级计算机通信,但现在欧阳尚书从中作梗,这个问题怕是得你来了“。

李将军找到了你,并许诺你解出来之后可以去大唐东市喝GoGo奶茶,他买单。

第1180题的题解