Description

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

Input

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

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

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

Output

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

Sample Input

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

Sample Output

2
7

HINT

Source

　　資格賽

Solution

　　裸LCA，看不懂代碼的人都是　　　　

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct edge
 4 {
 5     int v, w, nxt;
 6 }e[2005];
 7 struct query
 8 {
 9     int u, v, nxt;
10 }q[2005];
11 int efst[1005], qfst[1005], fa[1005], lca[1005], dis[1005];
12 bool vis[1005];
13  
14 void addedge(int i, int u, int v, int w)
15 {
16     e[i] = (edge){v, w, efst[u]}, efst[u] = i;
17 }
18  
19 void addquery(int i, int u, int v)
20 {
21     q[i] = (query){u, v, qfst[u]}, qfst[u] = i;
22 }
23  
24 int get_dis(int i)
25 {
26     return dis[q[i << 1].u] + dis[q[i << 1].v] - 2 * dis[lca[i]];
27 }
28  
29 int getfa(int x)
30 {
31     return fa[x] = x == fa[x] ? x : getfa(fa[x]);
32 }
33  
34 void Tarjan(int u)
35 {
36     fa[u] = u, vis[u] = true;
37     for(int i = efst[u]; i; i = e[i].nxt)
38         if(!vis[e[i].v])
39         {
40             dis[e[i].v] = dis[u] + e[i].w;
41             Tarjan(e[i].v);
42             fa[e[i].v] = u;
43         }
44     for(int i = qfst[u]; i; i = q[i].nxt)
45     {
46         int v = q[i].u == u ? q[i].v : q[i].u;
47         if(vis[v]) lca[i >> 1] = getfa(fa[v]);
48     }
49 }
50  
51 int main()
52 {
53     int n, q, u, v, w;
54     cin >> n >> q;
55     for(int i = 1; i < n; i++)
56     {
57         cin >> u >> v >> w;
58         addedge(i << 1, u, v, w);
59         addedge(i << 1 | 1, v, u, w);
60     }
61     for(int i = 1; i <= q; i++)
62     {
63         cin >> u >> v;
64         addquery(i << 1, u, v);
65         addquery(i << 1 | 1, v, u);
66     }
67     Tarjan(1);
68     for(int i = 1; i <= q; i++)
69         cout << get_dis(i) << endl;
70     return 0;
71 }

View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/CtrlCV/p/5491696.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ1602] [Usaco2008 Oct] 牧场行走 (LCA)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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