91 lines
2.4 KiB
C++
91 lines
2.4 KiB
C++
/* lanqiao3516 景区导游(LCA)
|
||
|
||
LCA-最近公共祖先
|
||
比如原本的遍历顺序是 a->b->c, 总路径长度为sum，若要跳过b，则新的路径长度为
|
||
sum-d(a,b)-d(b,c)+d(a,c)
|
||
其中 d(a,b)、d(b,c)、d(a,c)使用LCA求解更快
|
||
若要求u->v的路径长度, 等于求u-> root + v -> root - 2*(root->LCA(u ,v))
|
||
即分别从u和v走到根结点，再减去2倍的根结点到 (u,v) 的最近公共祖先的路径长度
|
||
倍增法求LCA时间复杂度-O(nlogn), 单次LCA查询时间复杂度-O(1ogn), k次查询时间复杂度-O(klogn)
|
||
总时间复杂度O((n+k)1ogn)由于n,k同級, 该算法时间复杂度为O(nlogn)
|
||
*/
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
const int N = 1e5 + 10;
|
||
int n, k;
|
||
|
||
// 邻接表存图
|
||
vector<pair<int, int>> g[N];
|
||
int deep[N]; // 深度数组
|
||
int fa[N][21]; // 倍增数组, fa[i][j]表示从i节点开始跳2^j步可到达的节点
|
||
int p[N]; // 原始的游览路线
|
||
int d[N]; // d[i]存储i到根节点的距离
|
||
|
||
// 预处理深度数组
|
||
void dfs(int u, int father){
|
||
deep[u] = deep[father] + 1;
|
||
fa[u][0] = father;
|
||
for(int i = 1; i <= 20; i++){
|
||
fa[u][i] = fa[fa[u][i-1]][i-1];
|
||
}
|
||
for(int i = 0; i < g[u].size(); i++){
|
||
int v = g[u][i].first, w = g[u][i].second;
|
||
if(v == father) continue;
|
||
d[v] = d[u] + w;
|
||
dfs(v, u);
|
||
}
|
||
}
|
||
// 倍增求LCA模版
|
||
int LCA(int x, int y){
|
||
if(deep[x] < deep[y]) swap(x, y);
|
||
for(int i = 20; i >= 0; i--){
|
||
if(deep[fa[x][i]] >= deep[y]){
|
||
x = fa[x][i];
|
||
}
|
||
}
|
||
if(x == y) return x;
|
||
for(int i = 20; i >= 0; i--){
|
||
if(fa[x][i] != fa[y][i]){
|
||
x = fa[x][i], y = fa[y][i];
|
||
}
|
||
}
|
||
return fa[x][0];
|
||
}
|
||
// 计算x和y的距离
|
||
int calc(int x, int y){
|
||
if(x == 0 || y == 0) return 0;
|
||
return d[x] + d[y] - 2*d[LCA(x, y)];
|
||
}
|
||
|
||
|
||
signed main(){
|
||
cin >> n >> k;
|
||
for(int i = 1; i < n; i++){
|
||
int u, v, w; cin >> u >> v >> w;
|
||
g[u].push_back({v, w});
|
||
g[v].push_back({u, w});
|
||
}
|
||
dfs(1, 0);
|
||
int sum = 0;
|
||
for(int i = 1; i <= k; i++){
|
||
cin >> p[i];
|
||
sum += calc(p[i], p[i-1]);
|
||
}
|
||
for(int i = 1; i <= k; i++){ // 循环枚举去除第i个节点
|
||
int d1 = calc(p[i], p[i-1]);
|
||
int d2 = calc(p[i], p[i+1]);
|
||
int d3 = calc(p[i-1], p[i+1]);
|
||
cout << sum - d1 - d2 + d3 << " ";
|
||
}
|
||
return 0;
|
||
}
|
||
/* test sanples -> 10 7 13 14
|
||
6 4
|
||
1 2 1
|
||
1 3 1
|
||
3 4 2
|
||
3 5 2
|
||
4 6 3
|
||
2 6 5 1
|
||
*/ |