首页 > 代码库 > LCA距离

LCA距离

2024-11-01 03:05:42   205人阅读

 

 

Problem Description
There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can‘t visit a place twice) between every two houses. Yout task is to answer all these curious people.
 

 

Input
First line is a single integer T(T<=10), indicating the number of test cases.
  For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
  Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
 

 

Output
For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.
 

 

Sample Input
2
3 2
1 2 10
3 1 15
1 2 2
3 2
 
2
1 2 100
1 2
2 1
 

 

Sample Output
10
25
100
100
 
 
n个定点，每个点之间有距离，q次询问，求两点之间的最短路径，和最小生成树有所不同的是n个定点只有n-1个边使之相通，没有连成圆。
用LCA做时，连点之间的距离等于根节点到两点距离之和 减去根节点到点v点的祖先的距离的两倍 即ans[query[u][i].w] = dis[u]+dis[v]-2*dis[findset(v)];
 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <vector>
 5 using namespace std;
 6 const int N = 40010;
 7 struct Nod{
 8     int to, w;
 9     Nod(int a = 0, int b = 0){
10         to = a; w = b;
11     }
12 };
13 int ans[N];
14 int par[N],vis[N],mark[N],dis[N];
15 int n,m;
16 vector<Nod> mp[N];
17 vector<Nod> query[N];
18 void init(){
19     for(int i = 0; i <= n; i ++){
20         mp[i].clear();
21         query[i].clear();
22         vis[i] = mark[i] = 0;
23         par[i] = i;
24     }
25     memset(ans,-1,sizeof(ans));
26 }
27 int findset(int x){
28     if(x != par[x]) par[x] = findset(par[x]);
29     return par[x];
30 }
31 
32 void dfs(int u){
33     for(int i = 0; i < query[u].size(); i ++){
34         int v = query[u][i].to;
35         if(vis[v]&&ans[query[u][i].w]==-1&&!mark[findset(v)]){
36             ans[query[u][i].w] = dis[u]+dis[v]-2*dis[findset(v)];
37         }
38     }
39     for(int i = 0; i < mp[u].size(); i++){
40         int v = mp[u][i].to;
41         if(!vis[v]){
42             vis[v] = 1;
43             dis[v] = dis[u]+mp[u][i].w;
44             dfs(v);
45             par[v] = u;
46         }
47     }
48 }
49 
50 int main(){
51     int t;
52     scanf("%d",&t);
53     while(t--){
54         scanf("%d%d",&n,&m);
55         init();
56         int x, y, z;
57         for(int i = 0; i < n-1; i ++){
58             scanf("%d%d%d",&x,&y,&z);
59             mp[x].push_back(Nod(y,z));
60             mp[y].push_back(Nod(x,z));
61         }
62         for(int i = 1; i <= m; i ++){
63             scanf("%d%d",&x,&y);
64             query[x].push_back(Nod(y,i));
65             query[y].push_back(Nod(x,i));
66         }
67         for(int i = 1; i <= n; i ++){            
68             if(!vis[i]){
69                 printf("%d+++\n",i);
70                 vis[i] = 1;
71                 dis[i] = 0;
72                 dfs(i);
73                 mark[i] = 1;
74             }
75         }
76         for(int i = 1; i <= m; i ++){
77             printf("%d\n",ans[i]);
78         }
79     }
80     return 0;
81 }

 

LCA距离


联系
我们