51nod 2621 樹上距離 （倍增+ LCA 模板）

有一棵n個節(jié)點的無向樹，每條邊有一個邊權，現(xiàn)在有q次詢問，每次詢問給出兩個點，求這兩個點之間的簡單路徑上的邊權和是多少。

輸入格式
第1行：兩個整數(shù)n和q,n表示這棵樹的節(jié)點個數(shù)，q表示查詢的次數(shù)。(1<=n,q<=100000) 第2行~第n行：每行有三個整數(shù)u,v,w，表示u與v之間有一條權值為w的邊。(1<=w<=100000) 第n+1行~n+q行：每行有兩個正整數(shù)x,y，表示要查詢的兩個點的編號。
輸出格式
第1行-第q行：每行輸出一個數(shù)，表示那要查詢的兩點之間的簡單路徑上的邊權和。
輸入樣例
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
輸出樣例
2
7
樣例解釋

如圖所示的數(shù)據(jù)中：

1號節(jié)點和2號節(jié)點之間的距離為：2

2號節(jié)點和3號節(jié)點之間的距離為：2+2+3=7

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<set> #include<map> #include<cstring> #define ll long long using namespace std;const int N = 1e5 +10; int n, q; int f[N][30], dep[N]; ll dis[N];struct Edge{int to, cost; }; vector<Edge> g[N];void dfs(int u, int fa){f[u][0] = fa; // for (int i = 1; i <= 20; i++)f[u][i] = f[f[u][i-1]][i-1];for(int i = 0; i < g[u].size(); i++){Edge e = g[u][i];if(e.to != fa){dis[e.to] = dis[u] + e.cost;dep[e.to] = dep[u] + 1;dfs(e.to, u);}} }void init(){int u, v, w;for(int i = 1; i <= n - 1; i++){cin >> u >> v >> w;g[u].push_back(Edge{v, w});g[v].push_back(Edge{u, w});}dis[1] = 0;dep[1] = 0;dfs(1, 0); }int lca (int u , int v){if(dep[u] < dep[v]) swap(u, v);int k = dep[u] - dep[v];for(int i = 20; i >= 0 ; i--){if((k >> i) & 1)u = f[u][i];}if(u == v) return u;for(int i = 20; i >= 0; i--){if(f[u][i] != f[v][i]){u = f[u][i];v = f[v][i];}}return f[u][0]; } int main(){cin >> n >> q;init();int u, v;while(q--){cin >> u >> v;cout << dis[u] + dis[v] - 2 * dis[lca(u, v)] << endl;} }

總結

以上是生活随笔為你收集整理的51nod 2621 树上距离 （倍增+ LCA 模板）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。