Problem Description
On a tree, the edge weight of the tree is
1
1
1 ,
S
e
r
e
no
a
d
e
Serenade
Serenade and
R
h
a
p
the s
o
d
y
Rhapsody
Rhapsodya from their respective starting points
S
a
S_a
Sa? ,
S
b
S_b
Sb? towards the end
T
a
T_a
Ta? ,
T
b
T_b
Tb? Do a back and forth motion.
beg
S
e
r
e
no
a
d
e
Serenade
Serenade and
R
h
a
p
the s
o
y
a
Rhapsoya
Rhapsoya’s earliest encounter node on the node.
Input
Enter an integer on the first line
t
t
t
(
1
≤
t
≤
500
)
(1 \le t \le 500)
(1≤t≤500), indicating the number of test groups.
Enter two integers on the next line
no
,
m
n,m
n,m
(
2
≤
no
,
m
≤
3
×
1
0
3
)
(2 \le n,m \le 3 \times 10^3)
(2≤n, m≤3×103), represents the number of nodes and the number of queries in the tree.
Next
no
?
1
n-1
n?1 lines input two integers in each line
u
,
v
u,v
u,v
(
1
≤
u
,
v
≤
no
,
u
=?
v
)
(1 \le u,v \le n,u\\
ot= v)
(1≤u,v≤n,u=v), indicating
u
,
v
u,v
There is an edge between u and v.
Next
m
m
m Enter four integers per line
S
a
,
T
a
,
S
b
,
T
b
S_a,T_a,S_b,T_b
Sa?,Ta?,Sb?,Tb?
(
1
≤
S
a
,
T
a
,
S
b
,
T
b
≤
no
,
S
a
=?
T
a
,
S
b
=?
T
b
)
(1 \le S_a,T_a,S_b,T_b \le n,S_a \\
ot= T_a,S_b \\
ot= T_b)
(1≤Sa?,Ta?,Sb?,Tb?≤n,Sa?=Ta?,Sb?=Tb?), means
S
e
r
e
no
a
d
e
Serenade
Serenade and
R
h
a
p
the s
o
d
y
Rhapsody
Rhapsodya’s respective beginning and end.
Data guaranteed not to exceed
20
20
20 groups
no
,
m
n,m
n,m over
400
400
400.
Output
For each query, output the corresponding node number, if it does not meet, output
?
1
-1
?1 .
Solution
Below
S
e
r
e
no
a
d
e
Serenade
Serenade and
R
h
a
p
the s
o
y
a
Rhapsoya
Rhapsoya is considered
a
a
a ,
b
b
b.
first if
a
a
a and
b
b
b to intersect, then
a
a
a The path from the start point to the end point must sum
b
b
b The path from start point to end point intersects. And for intersecting paths, since
no
no
n and
m
m
m only
3
×
1
0
3
3 \times 10^3
3×103 , we can directly force the
a
a
a and
b
b
The points on the path of b are respectively
+
1
+ 1
+ 1 , then we only need to consider the weight on the path as
2
2
2 points.
Then for whether a point can meet and seek
a
a
a and
b
b
The number of the earliest meeting steps of b, we discuss by category, let
a
l
0
,
a
l
1
al_0, al_1
al0?, al1? and
b
l
0
,
b
l
1
bl_0,bl_1
bl0?,bl1? is
a
a
a and
b
b
b the distance from the start and end point to the intersection point,
k
1
,
k
2
∈
N
+
k_1,k_2 \in N^ +
k1?,k2?∈N + , it is found that only
4
4
4 cases:
·
a
a
a walk out from the starting point with
b
b
b Out of the encounter from the starting point.
2
k
1
×
(
a
l
0
+
a
l
1
)
+
a
l
0
=
2
k
2
×
(
b
l
0
+
b
l
1
)
+
b
l
0
2k_1 \times (al_0 + al_1) + al_0 = 2k_2 \times (bl_0 + bl_1) + bl_0
2k1?×(al0? + al1?) + al0?=2k2?×(bl0? + bl1?) + bl0?.
·
a
a
a walk out from the starting point with
b
b
b Out of the end meet.
2
k
1
×
(
a
l
0
+
a
l
1
)
+
a
l
0
=
(
2
k
2
?
1
)
×
(
b
l
0
+
b
l
1
)
+
b
l
1
2k_1 \times (al_0 + al_1) + al_0 = (2k_2-1) \times (bl_0 + bl_1) + bl_1
2k1?×(al0? + al1?) + al0?=(2k21)×(bl0? + bl1?) + bl1?.
·
a
a
a walks from the end point with
b
b
b Out of the encounter with the starting point.
(
2
k
1
?
1
)
×
(
a
l
0
+
a
l
1
)
+
a
l
1
=
2
k
2
×
(
b
l
0
+
b
l
1
)
+
b
l
0
(2k_1-1) \times (al_0 + al_1) + al_1 = 2k_2 \times (bl_0 + bl_1) + bl_0
(2k11)×(al0? + al1?) + al1?=2k2?×(bl0? + bl1?) + bl0?.
·
a
a
a walks from the end point with
b
b
b meets with end point out.
(
2
k
1
?
1
)
×
(
a
l
0
+
a
l
1
)
+
a
l
1
=
(
2
k
2
?
1
)
×
(
b
l
0
+
b
l
1
)
+
b
l
1
(2k_1-1) \times (al_0 + al_1) + al_1 = (2k_2-1) \times (bl_0 + bl_1) + bl_1
(2k11)×(al0? + al1?) + al1?=(2k21)×(bl0? + bl1?) + bl1?.
For how to calculate the minimum number of steps and whether they intersect, we only need
e
x
g
c
d
exgcd
exgcd calculates
k
1
k_1
k1? and
k
2
k_2
The value of k2?, how to calculate the corresponding minimum integer.
Complexity analysis:
O
(
20
no
m
l
o
g
no
)
O(20nmlogn)
O(20nmlogn), the surface complexity may even reach
2
×
1
0
9
2 \times 10^9
2×109, but observe
e
x
g
c
d
exgcd
exgcd does not actually reach
l
o
g
no
logn
logn , although with the possibility
5
5
5 times the constant (?), but still can mysteriously pass this question. . .
Code
#include <bits/stdc + + .h>
#define endl '\\
'
using namespace std;
const int N = 3e3 + 10, M = 6e3 + 10;
int meet_point, step;//Optimal meeting point and steps
vector<int>a(2), b(2), al(2), bl(2);
int acs[N];
int head[N], e[M], ne[M], idx;
int fa[N], dep[N], siz[N], wson[N], top[N];
void clear(int n) {<!-- -->
idx = 0;
for (int i = 0; i <= n + 5; i + + ) head[i] = -1, wson[i] = 0;
}
inline void addedge(int a, int b) {<!-- -->
e[idx] = b, ne[idx] = head[a], head[a] = idx++;
}
int exgcd(int a, int b, int & amp; x, int & amp; y) {<!-- -->
if (!b) {<!-- -->
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
//Tree section LCA
void dfs1(int u, int father) {<!-- -->
dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;
for (int i = head[u]; i != -1; i = ne[i]) {<!-- -->
int v = e[i];
if (v == father) continue;
dfs1(v, u);
if (siz[v] > size[wson[u]])wson[u] = v;
siz[u] + = siz[v];
}
}
void dfs2(int u, int chead) {<!-- -->
top[u] = chead;
if (wson[u])dfs2(wson[u], chead);
for (int i = head[u]; i != -1; i = ne[i]) {<!-- -->
int v = e[i];
if (v == fa[u] || v == wson[u])continue;
dfs2(v, v);
}
}
int lca(int a, int b) {<!-- -->
while (top[a] != top[b]) {<!-- -->
if (dep[top[a]] < dep[top[b]])b = fa[top[b]];
else a = fa[top[a]];
}
return dep[a] < dep[b] ? a : b;
}
void add_point(int u, int father) {<!-- -->//point on the path from u to father + 1
while (u != father) {<!-- -->
acs[u] + + ;
u = fa[u];
}
}
int dis(int x, int y) {<!-- -->//Find the distance from x to y
int anc = lca(x, y);
return dep[x] + dep[y] - 2 * dep[anc];
}
void judge_meet(int cross, int left, int right) {<!-- -->//Judge whether to meet and count the answers
int x0, y0, c, d, dx, dy;
int lena = 2 * (al[0] + al[1]), lenb = 2 * (bl[0] + bl[1]);
d = exgcd(lena, lenb, x0, y0);
dx = lenb / d, dy = lena / d;
c = right - left;
if (c % d == 0) {<!-- -->
int x = x0 * c / d, y = y0 * c / d;
x = (x % dx + dx) % dx;
y = (y % dy + dy) % dy;
y -= dy;
int val = min(lena * x + left, -lenb * y + right);
if (step > val) meet_point = cross, step = val;
}
}
void get_ans(int cross) {<!-- -->
al[0] = dis(a[0], cross), al[1] = dis(a[1], cross);//al[0], al[1] represent the distance from the starting point of point a to the intersection point
bl[0] = dis(b[0], cross), bl[1] = dis(b[1], cross);//bl[0], bl[1] represent the distance from the starting point and end point of point b to the intersection point
judge_meet(cross, al[0], bl[0]);
judge_meet(cross, al[0], bl[0] + 2 * bl[1]);
judge_meet(cross, al[0] + 2 * al[1], bl[0] + 2 * bl[1]);
judge_meet(cross, al[0] + 2 * al[1], bl[0]);
}
void solve() {<!-- -->
int n, m;
cin >> n >> m;
clear(n);
for (int i = 1; i <= n - 1; i ++ ) {<!-- -->
int u, v;
cin >> u >> v;
addedge(u, v), addedge(v, u);
}
dfs1(1, 0);
dfs2(1, 1);
while (m--) {<!-- -->
meet_point = -1;
step = 2e9;
for (int i = 1; i <= n; i ++ )acs[i] = 0;
cin >> a[0] >> a[1] >> b[0] >> b[1];
int x = lca(a[0], a[1]), y = lca(b[0], b[1]);
add_point(a[0], x), add_point(a[1], x), acs[x] + + ;
add_point(b[0], y), add_point(b[1], y), acs[y] + + ;
for (int i = 1; i <= n; i + + ) if (acs[i] >= 2)get_ans(i);
cout << meet_point << endl;
}
}
signed main() {<!-- -->
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)solve();
}