How far away ？
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18191 Accepted Submission(s): 7072
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.
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
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
25
100
100
Source
- LCA模板题
- 这里两种代码，一种离线tarjan一种在线RMQ+ST
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long LL ;
typedef unsigned long long ULL ;
const int maxn = 1e5 + ;
const int inf = 0x3f3f3f3f ;
const int npos = - ;
const int mod = 1e9 + ;
const int mxx = + ;
const double eps = 1e- ;
const double PI = acos(-1.0) ; /* LCA + ST + RMQ Online */
struct node{
int v, next;
LL w;
};
node edge[maxn<<];
int fac[];
int vis[maxn];
int head[maxn<<], cnt;
int ver[maxn<<], dep[maxn<<], first[maxn], tot;
int dp[maxn<<][];
LL dis[maxn];
void addedge(int x, int y, LL z){
edge[cnt].v=y;
edge[cnt].w=z;
edge[cnt].next=head[x];
head[x]=cnt++;
}
void dfs(int u, int d){
tot++;
vis[u]=;
ver[tot]=u;
dep[tot]=d;
first[u]=tot;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
LL w=edge[i].w;
if(!vis[v]){
dis[v]=dis[u]+w;
dfs(v,d+);
tot++;
ver[tot]=u;
dep[tot]=d;
}
}
}
void ST(int n){
int k=(int)(log((double)n)/log(2.0));
for(int i=;i<=n;i++)
dp[i][]=i;
for(int j=;j<=k;j++)
for(int i=;i+fac[j]-<=n;i++){
int pl=dp[i][j-];
int pr=dp[i+fac[j-]][j-];
if(dep[pl]<dep[pr])
dp[i][j]=pl;
else
dp[i][j]=pr;
}
}
int RMQ(int l, int r){
int k=(int)(log((double)(r-l+))/log(2.0));
int pl=dp[l][k];
int pr=dp[r-fac[k]+][k];
if(dep[pl]<dep[pr])
return pl;
else
return pr;
}
int LCA(int u, int v){
int x=first[u];
int y=first[v];
if(x>y)swap(x,y);
return ver[RMQ(x,y)];
}
int T, n, m, u, v;
LL w;
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
for(int i=;i<;i++)
fac[i]=(<<i);
while(~scanf("%d",&T)){
while(T--){
scanf("%d %d",&n,&m);
cnt=;
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
for(int i=;i<n;i++){
scanf("%d %d %lld",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
dis[]=;
tot=;
dfs(,);
ST(tot);
while(m--){
scanf("%d %d",&u,&v);
printf("%lld\n",dis[u]+dis[v]-*dis[LCA(u,v)]);
}
}
}
return ;
}
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long LL ;
typedef unsigned long long ULL ;
const int maxn = 1e5 + ;
const int inf = 0x3f3f3f3f ;
const int npos = - ;
const int mod = 1e9 + ;
const int mxx = + ;
const double eps = 1e- ;
const double PI = acos(-1.0) ; /* Tarjan Offline */
struct node{
int v, next;
LL w;
};
node edge[maxn<<], ask[maxn<<];
int head0[maxn<<], cnt0;
int head1[maxn<<], cnt1;
int vis[maxn], fa[maxn];
LL ans[], dis[maxn];
void addedge(int x, int y, LL z, int flag){
if(flag){
ask[cnt1].v=y;
ask[cnt1].w=z;
ask[cnt1].next=head1[x];
head1[x]=cnt1++;
}else{
edge[cnt0].v=y;
edge[cnt0].w=z;
edge[cnt0].next=head0[x];
head0[x]=cnt0++;
}
}
int find(int u){
if(u==fa[u])
return u;
else
return fa[u]=find(fa[u]);
// return u==fa[u]?u:find(fa[u]);
}
void Union(int x, int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy)
fa[fy]=fx;
}
void Tarjan(int u){
vis[u]=;
fa[u]=u;
for(int i=head1[u];i!=-;i=ask[i].next){
int v=ask[i].v;
if(vis[v]){
int lca=find(v);
int id=ask[i].w;
ans[id]=dis[u]+dis[v]-*dis[lca];
}
}
for(int i=head0[u];i!=-;i=edge[i].next){
int v=edge[i].v;
LL w=edge[i].w;
if(!vis[v]){
dis[v]=dis[u]+w;
Tarjan(v);
Union(u,v);
}
}
}
int T, n, m, u, v;
LL w;
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(~scanf("%d",&T)){
while(T--){
scanf("%d %d",&n,&m);
cnt0=;
cnt1=;
memset(head0,-,sizeof(head0));
memset(head1,-,sizeof(head1));
memset(vis,,sizeof(vis));
for(int i=;i<n;i++){
scanf("%d %d %lld",&u,&v,&w);
addedge(u,v,w,);
addedge(v,u,w,);
}
for(int i=;i<=m;i++){
scanf("%d %d",&u,&v);
addedge(u,v,(LL)i,);
addedge(v,u,(LL)i,);
}
dis[]=;
Tarjan();
for(int i=;i<=m;i++)
printf("%lld\n",ans[i]);
}
}
return ;
}