How far away ?
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8712 Accepted Submission(s): 3047
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,每次询问u,v,设c是u,v的lca,那么答案就是dis[u]+dis[v]-2*dis[c],其中dis表示从根到节点的距离。详见代码:
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define MAX_N 40003
using namespace std; bool vis[MAX_N]; struct edge {
public:
int to;
long long cost; edge(int t, long long c) : to(t), cost(c) { } edge() { }
}; vector<edge> G[MAX_N];
int q,n,m; struct node {
public:
int p, v; node(int pp, int vv) : p(pp), v(vv) { } node() { }
}; vector<node> Q[MAX_N];
int lca[MAX_N], ancestor[MAX_N]; int T, cas = ; int father[MAX_N];
void init() {
for (int i = ; i <= n; i++)
father[i] = i;
} int Find(int u) {
if (u == father[u])return u;
else return father[u] = Find(father[u]);
} void unionSet(int u,int v) {
int x = Find(u), y = Find(v);
if (x == y)return;
father[x] = y;
} bool Same(int u,int v) {
return Find(u) == Find(v);
} long long dis[MAX_N]; void Tarjan(int u,int p) {
for (int i = ; i < G[u].size(); i++) {
int v = G[u][i].to;
if (v == p)continue;
dis[v] = dis[u] + G[u][i].cost;
Tarjan(v, u);
unionSet(u, v);
ancestor[Find(u)] = u;
}
vis[u] = ;
for (int i = ; i < Q[u].size(); i++) {
int v = Q[u][i].v;
if (vis[v])
lca[Q[u][i].p] = ancestor[Find(v)];
}
} pair<int, int> qu[MAX_N]; int main() {
//cin.sync_with_stdio(false);
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &q);
m = n - ;
init();
memset(vis, , sizeof(vis));
memset(ancestor, , sizeof(ancestor));
memset(dis, , sizeof(dis));
memset(lca, , sizeof(lca));
for (int i = ; i <= n; i++)G[i].clear();
for (int i = ; i <= n; i++)Q[i].clear(); for (int i = ; i < m; i++) {
int u, v;
long long c;
scanf("%d%d%I64d", &u, &v, &c);
G[u].push_back(edge(v, c));
G[v].push_back(edge(u, c));
} for (int i = ; i < q; i++) {
int u, v;
scanf("%d%d", &u, &v);
qu[i] = make_pair(u, v);
Q[u].push_back(node(i, v));
Q[v].push_back(node(i, u));
}
Tarjan(, ); for (int i = ; i < q; i++)
printf("%I64d\n", dis[qu[i].first] + dis[qu[i].second] - * dis[lca[i]]);
}
return ;
}