Дано дерево с N вершинами и N-1 ненаправленными ребрами.1 <= N <= 250000 Необходимо выполнить определенные запросы.1 <= Q <= 10 ^ 5 В каждом запросе нам будут даны две вершины, скажем, a и b.Мы должны указать количество пар вершин, чтобы путь между ними содержал ровно одну общую вершину с вершинами, присутствующими на пути между вершинами a и b.Например: N = 6. Так N-1 ребер .--> 1 2, 1 3, 1 4, 2 5, 2 6. (Значение 1 связано с 2,3,4 и 2 связано с 1,5, 6)
Пусть наш запрос будет a и b -> 4 5.
Ответ будет 6. (Значит, в графе существует 6 пар вершин с заданным условием)6 пар: 1 1, 2 2, 4 4, 5 5, 1 3, 2 6.
Я обдумывал этот вопрос в течение 2 дней, но я не могу найти идеальной логики для этого.Сначала я подумал, что мы можем найти с помощью LCA (наименьшего общего предка), но потом я не смог найти, как.
Пожалуйста, помогите мне получить некоторую логику, чтобы я мог ее эффективно решить.