{"problem":{"name":"宿命 | Regulation of Destiny","description":{"content":"A 国为了防御 B 国的进攻，准备兴建一系列防御措施。 A 国有 $n$ 艘恒星级战舰，这些战舰无论如何都是要被保护的。为了节省材料，总司令用了 $n-1$ 条双向加速通道将这些战舰连接了起来。每个战舰有两个属性 $a_i,b_i$，分别代表战舰的人口数，科技程度。 在每艘战舰上有两种防御措施可以选择。你可以选择建设其中的一种，也可以选择不建设，但不能两种都建设。 在 $i$ 号战舰上建设 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":600,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8970"},"statements":[{"statement_type":"Markdown","content":"A 国为了防御 B 国的进攻，准备兴建一系列防御措施。\n\nA 国有 $n$ 艘恒星级战舰，这些战舰无论如何都是要被保护的。为了节省材料，总司令用了 $n-1$ 条双向加速通道将这些战舰连接了起来。每个战舰有两个属性 $a_i,b_i$，分别代表战舰的人口数，科技程度。\n\n在每艘战舰上有两种防御措施可以选择。你可以选择建设其中的一种，也可以选择不建设，但不能两种都建设。\n\n在 $i$ 号战舰上建设 I 类防御措施需要 $a_i$ 的金钱，可以保护 $i$ 号战舰本身和与其直接相连的战舰。\n\n在 $i$ 号战舰上建设 II 类防御措施需要 $b_i$ 的金钱，可以保护 $i$ 号战舰本身以及所有与 $i$ 号战舰的距离**恰好**为 $r$ 的战舰。\n\n定义战舰 $u$ 和战舰 $v$ 的距离为从 $u$ 到 $v$ 需要经过最少多少条加速通道。\n\n现在，请你求出保护所有战舰需要的最少金钱。\n\n## Input\n\n第一行，两个正整数 $n, r$。\n\n接下来 $n-1$ 行，每行两个正整数 $u, v$，代表一条通道所连接的两艘战舰编号为 $u, v$。\n\n接下来 $n$ 行，第 $i$ 行两个正整数 $a_i, b_i$，分别表示在 $i$ 号战舰上建设 I 类和 II 类防御措施所需要的金钱。\n\n## Output\n\n一行，一个整数，表示保护所有战舰需要的最少金钱。\n\n[samples]\n\n## Background\n\n压抑是有实质的，从躯壳到内脏，密不透风地包裹，药物仅仅像缝隙里挤进去的一滴水，浇不灭深幽的火焰。\n\n时间治愈不了一切，它只把泥泞日复一日地堆积。她的眼睛没有焦点，偶尔仿佛睡梦中惊醒，喊我的名字。\n\n街道乱糟糟，各家店铺放着音乐，公交车轮胎碾过柏油路，小孩打闹，玻璃瓶砸碎，电瓶车相撞……但我清楚地听见自己的呼吸声。后视镜里，我又一次看到她没有焦点的眼神，裹住眼球的眼泪，水的表面张力“嗒”的一声失效。\n\n撕开雨天，潜入他乡，所向往的尽头是天堂。\n\n浅蓝天光，云层泛紫，微弱的灯光嵌进夕阳。\n \n----\n \n \n “…你知道吗，所谓的力量，其实，就是心中的执念。”\n \n “执念？”\n \n “是啊…就是，必须要做的事，必须守护的人，必须…”\n \n “实现的心愿。”\n \n “那么…你心中有这样的执念吗？”\n \n “呃……有啊！我的执念，就是保护姐姐！”\n \n “傻小子，想保护你姐，等下辈子再说吧”\n \n\n## Note\n\n**【样例解释 \\#1】**\n\n在 $1$ 号战舰上建设任意一种防御措施，所花金钱为 $1$。\n\n---\n\n**【样例解释 \\#2】**\n\n在 $1$ 号战舰上建设 I 类防御措施，所花金钱为 $2$。\n\n---\n\n**【样例解释 \\#3】**\n\n在 $1,2$ 号战舰上各建设一个 II 类防御措施，所花金钱为 $2$。\n\n------------\n\n**【数据范围】**\n\n**本题采用捆绑测试且使用子任务依赖。**\n\n| 子任务编号 | $n \\le$ | $r \\le$ | 分值 |\n| :-----------: | :-----------: | :-----------: | :-----------: |\n| 1 | $10$ | $5$ | 5 |\n| 2 | $200$ | $1$ | 5 |\n| 3 | $20$ | $7$ | 10 |\n| 4 | $100$ | $2$ | 8 |\n| 5 | $100$ | $4$ | 11 |\n| 6 | $100$ | $5$ | 8 |\n| 7 | $200$ | $6$ | 34 |\n| 8 | $200$ | $7$ | 19 |\n\n对于 $100\\%$ 的数据，$1 \\le n \\le 200$，$1 \\le r \\le 7$，$1 \\le a_i, b_i \\le {10}^9$，$1 \\le u, v \\le n$，保证任意两艘战舰可以通过若干条加速通道到达。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8970","tags":["洛谷原创","O2优化","分治","树形 DP","洛谷月赛","状压 DP"],"sample_group":[["1 1\n1 1\n","1\n"],["3 2\n1 2\n1 3\n2 1\n111111 1111111\n3 45\n","2\n"],["4 2\n1 2\n1 3\n2 4\n3 1\n2 1\n1 1\n1 2\n","2\n"]],"created_at":"2026-03-03 11:09:25"}}