冴月麟和魏潇承是好朋友
冴月麟为了守护幻想乡,而制造了幻想乡的倒影将真实的幻想乡封印了。任何人都无法进入真实的幻想乡了但是她给前来救她的魏潇承留叻一个线索。
她设置了一棵树(有根)树的每一条边上具有割掉该边的代价。
魏潇承需要计算出割开这棵树的最小代价这就是冴月麟囷魏潇承约定的小秘密。
注:所谓割开一棵有根树就是删除若干条边,使得任何任何叶子节点和根节点不连通
输入第一行两个整数n,S表示树的节点个数和根
接下来n-1行每行三个整数a、b、c,表示a、b之间有一条代价为c的边
输出包含一行,一个整数表示所求最小代价。
令f[x]為切断x与其叶子节点的最小费用
如果切割该边的费用小于f[v]那么切这条边就行了
发布了0 篇原创文章 · 获赞 7 · 访问量 8万+