#110. 「LCA模板」 想要传达给你的爱恋

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Woshiluo

题目描述

不愿意听题目背景瞎说的可以直接跳到输入格式

7.jpg

那些熠熠生辉的景象被歌声唤醒,浮现在疲倦的脑海里。 我们为了些十分渺小的事物,全力度过了那段岁月。 就算可笑,就算笨拙,也义无反顾。 我全力追逐着你。 所以回忆起来才觉得这般耀眼。 如果这段岁月也是Glorious Days...... 那我们所能做的,只有一直全力以赴了吧。

国见洸太郎坐在公园的板凳上半睡半醒,仿佛听到了姬野星奏的脚步声,但当他一睁眼,环顾四周,又未能见到心上人的影子,根据之前的故事直觉,国见洸太郎相信姬野星奏一定回到了御影之丘,他决定从公园前往御影之丘车站碰碰运气

如国见洸太郎所想,姬野星奏确确实实在御影之丘,但是她已经说过了,不会回到国见洸太郎身边,所以她希望到达车站后就走人,但她依然希望在这个小镇中多停留一阵,所以移动的速度远比国见洸太郎慢

御影之丘可以看做一棵有 n 个节点的树然后,御影之丘车站为一号节点

国见洸太郎担心自己会因为走的太快从而错过姬野星奏,但是他已经在御影之丘生活了二十多年,无论在哪里都有认识的人,所以他在走的时候会给那个地方的熟人打个招呼,注意一下

鉴于姬野星奏的反应有点小慢,我们假设等国见洸太郎到了御影之丘车站才会开始行动

请问,姬野星奏第一次被国见洸太郎和他的伙伴们发现是在几号节点

输入格式

第一行两个数字, n , m 表示这个树的大小,和询问组数

接下来 n - 1 行,每行两个数字 u, v 表示 u,v 之间有一条边接下来 m 行,每行两个数字 u,v ,表示公园的位置和姬野星奏的位置

输出格式

m 行,表示询问结果( lca(u,v)​ )

样例

样例输入1:

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

样例输出1:

4
1
1
1
1

数据范围与提示

n \leq 10^7 , m \leq 2000

彩蛋

说来 OI 界中这么多 Acg 背景的题目,竟然没有以「想要传达给你的爱恋」这个作为背景的,那么喜闻乐见,我来出吧!

实际上在原作当中,作者只写道 国见洸太郎坐在公园的板凳上半谁半醒,仿佛听到了姬野星奏的脚步声 这一部分,作为一个开放式结局,收尾了当时我看到这直接把手里自己的手机抛出去了,本题也算是一个同人(续作)短篇?

星之声,风之奏,俯首仰望御影丘
彩之虹,雨之音,携手相拥风雨后