How far away ？
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
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
Source
题目链接
题目描述
给定一个生成树，求任意两个结点的距离
解题思路
1.树上倍增法
- 时间复杂度：\(((n+m)log(n))\)
2.tarjan优化
本质：一种离线做法，并查集对“向上标记法”的优化
- 时间复杂度：\(o(n+m)\)
代码
- 常规代码
#include<bits/stdc++.h>
using namespace std;
const int N=40010;
vector<pair<int,int>>adj[N];//邻接表
int dist[N],d[N],f[N][20];//dist[i]:结点i到根节点的距离，d[i]:结点i的深度，
//f[i][j]:结点i向上走2^j步到达的结点
int T,n,m,x,y,z,t;
void bfs()
{
queue<int>q;
q.push(1);//设1为根节点
dist[1]=0;
d[1]=1;
while(q.size())
{
int u=q.front();
q.pop();
for(auto p:adj[u])
{
int v=p.first,w=p.second;
if(dist[v]||v==1)continue;//注意v==1的情况
d[v]=d[u]+1;
dist[v]=dist[u]+w;
f[v][0]=u;
for(int i=1;i<=t;i++)f[v][i]=f[f[v][i-1]][i-1];//注意，这里是递推式子，应该从小到大
q.push(v);
}
}
}
int lca(int x,int y)
{
if(d[x]>d[y])swap(x,y);
for(int i=t;i>=0;i--)
if(d[f[y][i]]>=d[x])y=f[y][i];
if(x==y)return x;
for(int i=t;i>=0;i--)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
t=log(n)/log(2)+1;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
adj[x].emplace_back(y,z);
adj[y].emplace_back(x,z);
}
bfs();//预处理
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",dist[x]+dist[y]-2*dist[lca(x,y)]);
}
for(int i=1;i<=n;i++)d[i]=0,dist[i]=0,adj[i].clear();//多组测试，清零
}
return 0;
}
- 高效代码
#include<bits/stdc++.h>
using namespace std;
const int N=40010;
vector<int>query[N],query_id[N];
vector<pair<int,int>>adj[N];
int T,n,m,x,y,z,fa[N],dist[N],ans[210],vis[N];//ans记录答案,v标记是否遍历
void add_query(int u,int v,int id)//query与query_id同步，离线记录
{
query[u].emplace_back(v),query_id[u].emplace_back(id);
query[v].emplace_back(u),query_id[v].emplace_back(id);
}
int get(int x)
{
if(x==fa[x])return x;
return fa[x]=get(fa[x]);
}
void tarjan(int u)
{
vis[u]=1;
for(auto p:adj[u])
{
int v=p.first,w=p.second;
if(vis[v])continue;
dist[v]=dist[u]+w;
tarjan(v);
fa[v]=u;
}
for(int i=0;i<query[u].size();i++)
{
int v=query[u][i],id=query_id[u][i];
if(vis[v]==2)//已回溯的点才有更新过的father
{
int lca=get(v);
ans[id]=dist[u]+dist[v]-2*dist[lca];
}
}
vis[u]=2;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
fa[i]=i;
dist[i]=vis[i]=0;
adj[i].clear();
query[i].clear();
query_id[i].clear();
}
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
adj[x].emplace_back(y,z);
adj[y].emplace_back(x,z);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(x==y)ans[i]=0;
else
add_query(x,y,i);
}
tarjan(1);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
return 0;
}