首页 > 其他分享 >abc070d <简单树上dfs>

abc070d <简单树上dfs>

时间:2023-07-10 16:46:38浏览次数:50  
标签:int abc070d cin dfs dep include adj

D - Transit Tree Path

// https://atcoder.jp/contests/abc070/tasks/abc070_d
// <简单树上dfs>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;
struct Node
{
    int v, w;
};
vector<Node> adj[N];
LL dep[N];

void dfs(int u, int p)
{
    for (auto [v, w]: adj[u])
    {
        if (v == p) continue;
        dep[v] = dep[u] + w;
        dfs(v, u);
    }
}

void solv()
{
    int n, a, b, c, q, k;
    cin >> n;
    for (int i = 1; i < n; i ++)
    {
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    cin >> q >> k;
    dfs(k, 0);
    while (q --)
    {
        cin >> a >> b;
        cout << dep[a] + dep[b] << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}

标签:int,abc070d,cin,dfs,dep,include,adj
From: https://www.cnblogs.com/o2iginal/p/17541532.html

相关文章