You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

138 lines
6.7 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
const int N = 500010, M = N << 1;
#define int long long
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int n; // n个节点
int k; // k个需要接的人
// 以下的五个数组,是在递归中维护的数据,只有准备了这些数据,才能保证各种情况下我们都能提供正确的解答
int mx1[N]; // u的子树中最长链的长度
int mx2[N]; // u的子树中次长链
int sz[N]; // 以u为根的子树中是否有人
int id[N]; // id[u]:u的最长链条出发第1个经过的节点是哪个节点
int up[N]; // 向上的最长路径不在u的子树内,而是向u的父节点方向走距离u最远的那个人的家到u的距离
// 根据黄海的习惯换根DP的第一次结果我喜欢记录到f[]中第二次的统计结果喜欢记录到g[]中
// 这一点可能与网上一些题解不太一致,请读者注意
int f[N]; // 以任意点为根(一般情况下我喜欢以节点1为根),记录:从u出发把u子树上的人都送回家再回到u所需要的时间
int g[N]; // 不管以哪点为根出发,记录从u出发把所有点都送回家再回到u的最短时间
/*
本题其实是两个子问题的综合题:
1、你可以挑选任意一个点作为根出发然后dfs走完全部的有人的节点然后返回到根这时当根节点确定时这个总时间是确定的。
时间的相关条件包括:走了哪些路径(一来一回走两遍),路径的边权值,是从哪个根出发的(这个很好理解,从一个离大家都近的地方出发,肯定比
从欧洲出发要快吧~)。
2、如果只是最终都要回到根那上面的逻辑跑多次以不同节点为根的dfs就行也就是暴力换根当然我们嫌人家O(N^2)太慢,也可以优化一下:
采用换根dp,两次dfs优化为O(N)的。
但这样肯定是不行的,原因是题目中隐藏了一个条件:最后一次送完人,不用回到根起点!!!
这个非常重要!!就是因为它才导致后面的讨论、存储统计信息非常麻烦!!!
*/
/*
第一次dfs,先递归子节点v利用子节点v提供的信息更新父节点u的统计信息
统计信息包括:
① mx1[u]:以u为根的子树中u可以走的最长距离.每次变更是通过mx1[u]=max(mx1[v]+w[i])更新的
② mx2[u]:以u为根的子树中u可以走的次长距离
③ id[u]: 以u为根的子树中当获取到u可以走的最长距离时它第一个经过的点记录到id[u]中
④ sz[u]: 以u为根的子树中有多少个需要接的人员
⑤ f[u]: 以u为根的子树中从u出发接完子树中所有人员并且返回到u所需要的时间
*/
void dfs1(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
dfs1(v, u); // 上来先递归u的子节点v,因为v中在初始化读入时已经初始化了sz[v]=1,所以可以利用这个进行更新sz[u]+=sum(sz[v])
if (sz[v] == 0) continue; // 如果v里面没有需要接的人那么以v为根的子树不会对u为根的子树产生贡献放过v子树
// 如果进入到这里说明v子树里面有需要接的人会对u为根的子树产生贡献需要讨论
f[u] += f[v] + 2 * w[i];
// v子树里有人那么v子树就一定要进去看看所以一来一回的w[i]省不下
// v里面到底需要花费多少时间记录在f[v]里了所以v子树的整体贡献=f[v]+2*w[i]
// 维护最长、次长、最长是经过哪个节点来的三件事
int x = mx1[v] + w[i]; // v在以v为根的子树中能走到的最长路径记录在mx1[v]里现在以子推父父亲的以u为根的子树中u能走到的最长路径记录到mx1[u]中
// 如果u的最长路径可能是通过v获取到的那么 mx1[u]=mx1[v]+w[i]
if (x >= mx1[u]) {
mx2[u] = mx1[u]; // 最长变为次长
mx1[u] = x; // mx1[v]+w[i]变为最长
id[u] = v; // 记录u的最长路径中第一个节点走的是v
} else if (x > mx2[u]) // 如果小于最长,大于次长(注意:这里不需要等号,等号没用,当然,加上也不错)
mx2[u] = x; // 更新次长
// 汇总父节点u的接人个数
sz[u] += sz[v];
}
}
/* 换根DP
统计信息(以父更子所以一般写作g[v])
① g[v] : 不再拘泥于只能向下统计也包括向上的统计信息全带上我想知道以v为根出发需要多长时间把所有人都送回家并且回到v点的时间是多少
② up[v]: v向上走的最远路径是多少
*/
void dfs2(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
/*
情况1
所有的节点都在v的子树内,那么,这里比较容易理解,因为所有节点都在子树内,
那么这两个答案自然就等价了,而非子树最长链也很显然为0
*/
if (sz[v] == k) {
g[v] = f[v],
up[v] = 0;
}
/*
v子树没有被标记的点那么一切都由父节点继承过了了
*/
else if (sz[v] == 0) {
g[v] = g[u] + 2 * w[i]; // 如果从v出发并且向u方向前进那么u的结果就是你的结果但是要加上两次跑路的代价
up[v] = max(up[u], mx1[u]) + w[i]; // 需要取u的上、下行最长路径PK+w[i]
}
// v子树有标记的点v子树外也有标记的点
else if (sz[v] && sz[v] != k) {
g[v] = g[u]; // 这个最难理解,见题解
if (id[u] == v) // 如果u的最长路径上第一个节点是v
up[v] = max(mx2[u], up[u]) + w[i];
else
up[v] = max(mx1[u], up[u]) + w[i];
}
// 套路
dfs2(v, u);
}
}
signed main() {
// 初始化链式前向星
memset(h, -1, sizeof h);
cin >> n >> k; // n个节点,要接k个人
for (int i = 1; i < n; i++) { // n-1条边
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
for (int i = 1; i <= k; i++) {
int x;
cin >> x;
sz[x] = 1; // x节点有一个人
}
// 第一次dfs
dfs1(1, 0);
g[1] = f[1];
// 第二次dfs
dfs2(1, 0);
// 遍历所有节点,以每个点为根出发,输出时间的最小值
for (int i = 1; i <= n; i++) cout << g[i] - max(up[i], mx1[i]) << endl;
}