SP1825 FTOUR2 - Free tour II

继两周年优惠旅行活动取得成功之后，SPOJ 旅行社在三周年之际再次推出了一次优惠旅行。 这次旅行将在太平洋上的神奇岛屿 ICPC 岛举办。岛上共有 $N$ 个景点（编号为 $1$ 到 $N$），游客可以在这些景点之间游览。连接景点的每条道路都有一个**观赏价值**，这个值可能是**负数**（表示这条路几乎没有值得欣赏的风景）。 这 $N$ 个景点以及连接它们的道路构成了一棵树。旅行路线需要选择**两个景点**分别作为起点和终点。 由于九月正值当地居民的节庆时期，一些景点会非常拥挤（称为**拥挤景点**）。因此，旅行社希望整条旅行路线中经过的**拥挤景点数量不超过 $K$ 个**（否则游客会太疲惫），同时希望路线上的**观赏价值总和尽可能大**。 换句话说，给定一棵树、整数 $K$ 以及 $M$ 个拥挤景点，请求出满足经过的拥挤景点数不超过 $K$ 的路径中，观赏价值总和最大的那一条。 需要注意： - 每个景点最多只能经过一次（即路径不能重复经过同一节点）。 - 起点和终点**可以是同一个景点**。

本题仅包含一组测试数据。 第一行包含三个整数 $N,K,M$，保证 $1\le N\le 2\times 10^5$，$0\le K\le M\le N$。 接下来 $M$ 行，每行一个整数，表示一个拥挤景点的编号。 最后 $N-1$ 行，每行包含三个整数 $a,b,i$，表示景点 $a$ 和 $b$ 之间有一条双向道路，其观赏价值为 $i$（$|i| \le 10^4$）。保证所有道路构成一棵树。

输出一个整数，表示满足经过的拥挤景点数量不超过 $K$ 的所有路径中，能够获得的最大观赏价值总和。

由 ChatCPT 5 翻译