luogu P3398 仓鼠找sugar
Description--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--
Description–
小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？
小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！
Input–
第一行两个正整数n和q，表示这棵树节点的个数和询问的个数。
接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。
接下来q行，每行四个正整数a、b、c和d，表示节点编号，也就是一次询问，其意义如上。
Output–
对于每个询问，如果有公共点，输出大写字母“Y”；否则输出“N”。
Sample Input–
5 5
2 5
4 2
1 3
1 4
5 1 5 1
2 2 1 4
4 1 3 4
3 1 1 5
3 5 1 4
Sample Output–
Y
N
Y
Y
Y
说明–
本题时限1s，内存限制128M，因新评测机速度较为接近NOIP评测机速度，请注意常数问题带来的影响。
20%的数据 n<=200,q<=200
40%的数据 n<=2000,q<=2000
70%的数据 n<=50000,q<=50000
100%的数据 n<=100000,q<=100000
解题思路–
a到b的距离 = lca(a, b)到a的距离（深度）+ lca(a, b)到b的距离 若两条路径相交，那一条路径的lca一定在另一条路径上（画一下就知道了） 也就是 a到b的距离 和 lca(c, d)到a的距离 + lca(c, d)到b的距离 相等（c , d也是一样的）
代码–
#include <iostream>
#include <cstdio>
using namespace std
;
int n
, q
, a
, b
, c
, d
, t
;
int ls
[100005], lg
[100005], dep
[100005], fa
[100005][35];
struct ooo
{
int to
, next
;
}f
[200005];
void dfs(int x
, int father
)
{
dep
[x
] = dep
[father
] + 1;
fa
[x
][0] = father
;
for (int i
= 1; i
< lg
[dep
[x
]]; ++i
)
fa
[x
][i
] = fa
[fa
[x
][i
- 1]][i
- 1];
for (int i
= ls
[x
]; i
; i
= f
[i
].next
)
if (f
[i
].to
!= father
)
dfs(f
[i
].to
, x
);
}
int lca(int x
, int y
)
{
if (dep
[x
] < dep
[y
]) swap(x
, y
);
while (dep
[x
] > dep
[y
])
x
= fa
[x
][lg
[dep
[x
] - dep
[y
]] - 1];
if (x
== y
) return x
;
for (int i
= lg
[dep
[x
]] - 1; i
>= 0; --i
)
if (fa
[x
][i
] != fa
[y
][i
])
x
= fa
[x
][i
], y
= fa
[y
][i
];
return fa
[x
][0];
}
int lu(int x
, int y
)
{
int z
= lca(x
, y
);
return dep
[x
] - dep
[z
] + dep
[y
] - dep
[z
];
}
void work()
{
int x
= lca(a
, b
);
int y
= lca(c
, d
);
if (lu(a
, b
) == lu(a
, y
) + lu
(b
, y
)) {putchar('Y'); return ;}
if (lu(c
, d
) == lu(c
, x
) + lu
(d
, x
)) {putchar('Y'); return ;}
putchar('N');
}
int main()
{
scanf("%d%d", &n
, &q
);
for (int i
= 1; i
< n
; ++i
)
{
scanf("%d%d", &a
, &b
);
f
[++t
] = (ooo
) {b
, ls
[a
]}, ls
[a
] = t
;
f
[++t
] = (ooo
) {a
, ls
[b
]}, ls
[b
] = t
;
}
for (int i
= 1; i
<= n
; ++i
)
lg
[i
] = lg
[i
- 1] + (1 << lg
[i
- 1] == i
);
dfs(1, 0);
for (int i
= 1; i
<= q
; ++i
)
{
scanf("%d%d%d%d", &a
, &b
, &c
, &d
);
work(); putchar(10);
}
return 0;
}
