Description

N頭牛（2<=n<=1000）別人被標記為1到n，在同樣被標記1到n的n塊土地上吃草，第i頭牛在第i塊牧場吃草。 這n塊土地被n-1條邊連接。 奶牛可以在邊上行走，第i條邊連接第Ai，Bi塊牧場，第i條邊的長度是Li（1<=Li<=10000）。 這些邊被安排成任意兩頭奶牛都可以通過這些邊到達的情況，所以說這是一棵樹。 這些奶牛是非常喜歡交際的，經常會去互相訪問,他們想讓你去幫助他們計算Q(1<=q<=1000)對奶牛之間的距離。

Input

*第一行：兩個被空格隔開的整數：N和Q

?*第二行到第n行：第i+1行有兩個被空格隔開的整數：AI，BI，LI

*第n+1行到n+Q行：每一行有兩個空格隔開的整數：P1，P2，表示兩頭奶牛的編號。

Output

*第1行到第Q行：每行輸出一個數，表示那兩頭奶牛之間的距離。

?

題解：?

刷水有益健康.?

?

Code:

#include <bits/stdc++.h> #define maxn 10000 #define setIO(s) freopen(s".in","r",stdin) using namespace std; int hd[maxn],to[maxn],nex[maxn],val[maxn],dep[maxn],f[23][maxn],len[maxn]; int cnt; void add(int u,int v,int c){nex[++cnt]=hd[u],hd[u]=cnt,to[cnt]=v,val[cnt]=c; } void dfs(int u,int fa){f[0][u]=fa; for(int i=1;i<=20;++i) f[i][u]=f[i-1][f[i-1][u]]; for(int i=hd[u];i;i=nex[i]) {if(to[i]==fa) continue; len[to[i]]=len[u]+1, dep[to[i]]=dep[u]+val[i],dfs(to[i],u); } } int lca(int a,int b){ if(len[a]>len[b]) swap(a,b); if(len[a]!=len[b]){for(int i=20;i>=0;--i) if(len[f[i][b]] >= len[a]) b=f[i][b]; }if(a==b) return a; for(int i=20;i>=0;--i) {if(f[i][a]!=f[i][b]) a=f[i][a],b=f[i][b];}return f[0][a]; } int dis(int a,int b){return dep[a]+dep[b]-(dep[lca(a,b)]<<1); } int main(){// setIO("input"); int n,q; scanf("%d%d",&n,&q);for(int i=1,a,b,c;i<n;++i){scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); }dfs(1,0); while(q--){int a,b; scanf("%d%d",&a,&b); printf("%d\n",dis(a,b)); }return 0; }

　　

轉載于:https://www.cnblogs.com/guangheli/p/10944212.html

總結

以上是生活随笔為你收集整理的BZOJ 1602: [Usaco2008 Oct]牧场行走 倍增裸题的全部內容，希望文章能夠幫你解決所遇到的問題。

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