Distance Queries

题目描述

给定一棵由 $n$ 个节点构成的树。 你的任务是处理 $q$ 个查询，形式为：节点 $a$ 和 $b$ 之间的距离是多少？

输入格式

输入的第一行包含两个整数 $n$ 和 $q$：节点数和查询数。节点编号为 $1,2,\ldots,n$。 接下来有 $n-1$ 行描述边。每行包含两个整数 $a$ 和 $b$：表示在节点 $a$ 和 $b$ 之间有一条边。 最后有 $q$ 行描述查询。每行包含两个整数 $a$ 和 $b$：询问节点 $a$ 和 $b$ 之间的距离是多少？

输出格式

输出 $q$ 个整数：每个查询的答案。

5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4

1
3
2

提示

$1 \le n, q \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES1135|树

来源

CSES1135|树