LUBENICA - Lubenica

The traffic network in a country consists of N cities (labeled with integers from 1 to N) and N-1 roads connecting the cities. There is a unique path between each pair of different cities, and we know the exact length of each road. Write a program that will, for each of the K given pairs of cities, find the length of the shortest and the length of the longest road on the path between the two cities.

Input

  • The first line of input contains an integer N, 2 ≤ N ≤ 100 000.
  • Each of the following N-1 lines contains three integers A, B and C meaning that there is a road of length C between city A and city B. The length of each road will be a positive integer less than or equal to 1 000 000. The next line contains an integer K, 1 ≤ K ≤ 100 000.
  • Each of the following K lines contains two different integers D and E – the labels of the two cities constituting one query.

Output

Each of the K lines of output should contain two integers – the lengths from the task description for the corresponding pair of the cities.

Example

Input
1 6 5 100
25
50
50
10
20
23

Output
100 200
50 150
50 100
Input
7
3 6 4
1 7 1
1 3 2
1 2 6
2 5 4
2 4 4
5
6 4
7 6
1 2
1 3
3 5

Output
2 6
1 4
6 6
2 2
2 6
Input
9
1 2 2
2 3 1
3 4 5
2 7 4
1 5 3
5 6 1
5 9 2
1 8 3
5
6 9
7 8
9 4
1 2
7 3

Output
1 2
2 4
1 5
2 2
1 4

Được gửi lên bởi:Jimmy
Ngày:2007-12-18
Thời gian chạy:1.210s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Croatian OI 2006

hide comments
2021-05-27 18:02:06
Tham khảo: https://vnspoj.github.io/problems/LUBENICA
2019-12-24 16:09:47
LCA
CLQD K12
2019-11-07 02:42:42
#include <bits/stdc++.h>

using namespace std;
int n,m,d[100001][20],b[100001][20],c[100001][20],pa[100001],h[100001];
bool f[100001];
vector < vector <int> > a(100001),a1(100001);
void dfs(int u)
{
f[u]=false;
for(int i=0;i<a[u].size();i++)
if(f[a[u][i]]==true)
{
b[a[u][i]][0]=a1[u][i];
c[a[u][i]][0]=a1[u][i];
pa[a[u][i]]=u;
h[a[u][i]]=h[u]+1;
dfs(a[u][i]);
}
}
int lca(int x,int y)
{
int kq1,kq2;
kq1=1e9;
kq2=1e9;
if(h[x]>h[y]) swap(x,y);
if(h[x]!=h[y])
for(int i=17;i>=0;i--)
if(h[d[y][i]]>=h[x])
{
kq1=min(kq1,b[y][i]);
y=d[y][i];
}
if(x==y) return kq1;
for(int i=17;i>=0;i--)
while(d[x][i]!=d[y][i])
{
kq1=min(kq1,b[y][i]);
kq2=min(kq2,b[x][i]);
x=d[x][i];
y=d[y][i];
}
kq1=min(kq1,b[y][0]);
kq2=min(kq2,b[x][0]);
return min(kq1,kq2);
}
int lca2(int x,int y)
{
int kq1,kq2;
kq1=0;
kq2=0;
if(h[x]>h[y]) swap(x,y);
if(h[x]!=h[y])
for(int i=17;i>=0;i--)
if(h[d[y][i]]>=h[x])
{
kq1=max(kq1,c[y][i]);
y=d[y][i];
}
if(x==y) return kq1;
for(int i=17;i>=0;i--)
while(d[x][i]!=d[y][i])
{
kq1=max(kq1,c[y][i]);
kq2=max(kq2,c[x][i]);
x=d[x][i];
y=d[y][i];
}
kq1=max(kq1,c[y][0]);
kq2=max(kq2,c[x][0]);
return max(kq1,kq2);
}
int main()
{
cin >> n;
for(int i=1;i<n;i++)
{
int x,y,z;
cin >> x >> y >> z;
a[x].push_back(y);
a[y].push_back(x);
a1[x].push_back(z);
a1[y].push_back(z);
f[i]=true;
}
f[n]=true;
h[1]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=17;j++)
{
b[i][j]=1e9;
c[i][j]=0;
}
dfs(1);
for(int i=1;i<=n;i++) d[i][0]=pa[i];
for(int j=1;j<=17;j++)
for(int i=1;i<=n;i++)
{
d[i][j]=d[d[i][j-1]][j-1];
}
for(int j=1;j<=17;j++)
for(int i=1;i<=n;i++)
{
b[i][j]=min(b[i][j-1],b[d[i][j-1]][j-1]);
c[i][j]=max(c[i][j-1],c[d[i][j-1]][j-1]);
}
cin >> m;
for(int i=1;i<=m;i++)
{
int x,y;
cin >> x >> y;
int k=lca(x,y);
int k2=lca2(x,y);
cout << k <<" "<< k2 << endl;
}
return 0;
}
2018-12-17 10:58:01
làm lại 1 đấm AC với LCA chạy lâu hơn 0.10 và tốn mem hơn HLD
frostpixel aka.How 2 AC
2018-11-18 15:12:54
First time tự đọc và cài HLD để rồi AC chỉ với 0.53 s ( trong đầu cứ nghĩ là dùng HLD thay vì LCA thường sẽ bị TLE ), một cảm giác thật là high ^_^ :))
2018-09-09 16:47:25
Bạn nào muốn tham khảo thì đây nha :v
http://bit.ly/2H6N2zl

Last edit: 2019-01-11 17:19:38
2018-06-17 08:55:21
code AC :https://bit.ly/2HSOTD3
2018-02-01 14:37:10
easy
2018-01-02 03:24:48
HLD 1 đấm AC
frostpixel aka.How 2 AC
2018-01-01 12:19:14
tao trâu cũng AC :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.