- 题目链接：仓鼠找sugar
- 题目思路：首先，我们知道，在一棵树上两个节点(x,y)的最短距离就是x->LCA(x,y)->y，那么我们可以得出，从x到y，LCA(x,y)是必经之点，那么对于四个点(x1,y1;x2,y2)来说，如果它们的最短路上有交点，则max(deep[LCA(x1,y1)]，deep[LCA(x2,y2)]）后的LCA一定在任意两个点的最短路上，那根据之前的结论，我们就求出任意两个点的LCA，就深度取max,如果不小于max(deep[LCA(x1,y1)], deep[LCA(x2,y2)])，那就说明合法，否则，就不合法。
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
using namespace std;
int sc() {
int xx=0,ff=1; char cch;
while(cch<'0'|| cch>'9') {
if(cch=='-') ff=-ff; cch=gc;
}
while(cch>='0'&& cch<='9') {
xx=xx*10+(cch-48); cch=gc;
}
return xx*ff;
}
struct TREE {
int next,to;
}tree[Maxn*2];
int n,m,cnt;
int head[Maxn],deep[Maxn];
int f[Maxn][22];
void ADD(int from,int to) {
tree[++cnt].next=head[from];
tree[cnt].to=to;
head[from]=cnt;
}
void D_F(int son,int fa) {
deep[son]=deep[fa]+1;
for(int i=0; i<=19; i++)
f[son][i+1]=f[f[son][i]][i];
for(int i=head[son]; i; i=tree[i].next) {
int to=tree[i].to;
if(to==fa) continue;
f[to][0]=son;
D_F(to,son);
}
}
int LCA(int x,int y) {
if(deep[x]<deep[y]) swap(x,y);
for(int i=20; i>=0; i--) {
if(deep[f[x][i]]>=deep[y])
x=f[x][i];
if(x==y) return x;
}
for(int i=20; i>=0; i--) {
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}
return f[x][0];
}
int main() {
n=sc(); m=sc();
for(int i=1; i<n; i++) {
int x=sc(),y=sc();
ADD(x,y); ADD(y,x);
}
D_F(1,0);
while(m--) {
int x1=sc(),y1=sc(),x2=sc(),y2=sc();
int mid1=LCA(x1,y1),mid2=LCA(x2,y2);
int MID=max(deep[mid1],deep[mid2]);
int maxx=max(deep[LCA(x1,x2)],max(deep[LCA(x1,y2)],max(deep[LCA(y1,x2)],deep[LCA(y1,y2)])));
if(maxx>=MID) printf("Y\n");
else printf("N\n");
}
return 0;
}