code

用户名：wjh31415926535

访问量：972

签　名：

等　　级
排　　名	26280
经　　验	579
参赛次数	1
文章发表	4
年　　龄	0
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

TA的其他文章

前驱后驱数组 + 优先队列
浏览：359

tarjan算法求lca
浏览：251

tarjan + lca + 树上差分
浏览：299

你可能喜欢

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

tarjan算法求lca

　　作者: code　　　　发表时间：2023-04-19 15:20:25 浏览：251　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-景区导游

# 代码
```cpp
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <string>
#include<functional>
#include <math.h>
#include <algorithm>
// #include<numeric>
#include<ctime>
#include <cstring>
#define lowbit(x) (-x) & x
#define ll long long
const int N = 1e6;
using namespace std;    
const int mod = 1e9 + 7;
struct node{
    int to,nxt, w;
}e[N];
int cnt = 0;
int head[N];
void add(int u, int v, int w){
    e[++cnt].nxt = head[u];
    e[cnt].to = v;
    e[cnt].w = w;
    head[u] = cnt;
}

void solve(){   
    int n,k;
    cin>>n>>k;
    for(int i  = 0; i < n - 1;++i){
        int u, v, w;
        cin>>u>>v>>w;
        add(u - 1, v - 1, w);
        add(v - 1, u - 1, w);
    }
    int a[k];
    for(int i = 0; i < k;++i)cin>>a[i],a[i] -=1;
    ll d[n];
    d[0] = 0;
    queue<pair<int,int>>q;
    q.push({0, -1});
    while(!q.empty()){
        auto p = q.front();
        int u = p.first;
        int fa = p.second;
        q.pop();
        for(int i = head[u]; i; i = e[i].nxt){
            int v = e[i].to;
            if(v == fa)continue;
            d[v] = d[u] + e[i].w;
            q.push({v,u});
        }
    }
    vector<int>query[n];
    for(int i = 1; i < k;++i){
        query[a[i - 1]].push_back(a[i]);
        query[a[i]].push_back(a[i -1]);
    }
    for(int i = 2; i < k;++i){
        query[a[i - 2]].push_back(a[i]);
        query[a[i]].push_back(a[i - 2]);
    }
    int f[n];
    map<ll,int>lca;
    for(int i = 0; i < n;++i)f[i] = i;
    vector<int>color(n, 0);
    function<int(int)>find = [&](int x)->int{return (f[x] == x)?x : f[x] = find(f[x]);};
    function<void(int ,int)>tarjan = [&](int u, int fa){
        color[u] = 1;
        for(int i = head[u]; i; i = e[i].nxt){
            int v = e[i].to;
            if(color[v] == 0){
                tarjan(v, u);
                f[v] = u;
            }
        }
        for(auto & p : query[u]){
            int v = p;
            if(color[v] == 2){
                int ppp = find(v);
                lca[((ll)u*(1ll<<32)+ v)] = ppp;
                lca[((ll)v*(1ll<<32) + u)] = ppp;
            }
        }
        color[u] = 2;
    };
    function<ll(int,int)>Lca = [&](int u, int v){
        return d[u] + d[v] - 2*d[lca[((ll)u*(1ll<<32) + v)]];
    };
    tarjan(0, -1);  
    ll sum = 0;
    for(int i = 0; i < k - 1;++i)sum += Lca(a[i], a[i + 1]);
    for(int i = 0; i < k; ++i){
        ll cur = sum;
        if(i != 0) {
            cur -= Lca(a[i] , a[i - 1]);
        }
        if(i != k - 1) cur -= Lca(a[i] , a[i + 1]);
        if(i != 0 && i != k - 1)cur += Lca(a[i - 1], a[i + 1]);
        cout<<cur<<" ";
    }
}   
int main(){ 
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--){
        solve();
    }
    return 0 ;
}   
```

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

code

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

假币问题（C++代码）（向上取整的一种处理方式）

tarjan算法求lca

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-计负均正（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

code

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

假币问题 （C++代码）（向上取整的一种处理方式）

tarjan算法求lca

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-计负均正 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

假币问题（C++代码）（向上取整的一种处理方式）

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C二级辅导-计负均正（C语言代码）

C二级辅导-阶乘数列（C语言代码）