P83827

一道难题 Tree

难度 5 级 初三 动态规划入门 树形
讨论 统计 1通过 2提交 50%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

冴月麟为了守护幻想乡,而制造了幻想乡的倒影,将真实的幻想乡封印了。任何人都无法进入真实的幻想乡了,但是她给前来救她的魏潇承留了一个线索。

她设置了一棵树(有根)。树的每一条边上具有割掉该边的代价。

魏潇承需要计算出割开这棵树的最小代价,这就是冴月麟和魏潇承约定的小秘密。

帮帮魏潇承吧。

注:所谓割开一棵有根树,就是删除若干条边,使得任何任何叶子节点和根节点不连通。

输入

输入第一行两个整数 n,\mathrm{root} 分别表示树的节点个数和树根。

接下来 n-1 行每行三个整数 a,b,c,表示 a,b 之间有一条代价为 c 的边。

输出

输出包含一行,一个整数,表示所求最小代价。

样例

样例 1
输入
4 1
1 2 1 
1 3 1
1 4 1
输出
3
样例 2
输入
4 1
1 2 3
2 3 1
3 4 2
输出
1

提示

数据范围及约定

  • 对于 20\% 的数据,n\le 10;
  • 对于 50\% 的数据,n \le 1000;
  • 对于 100\% 的数据,2\le n \le 100000,且边权是不大于 10^6 的非负整数。

来源

luogu

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交