Skip to content

1167: 喝奶茶!喝奶茶!

题目

题目描述

助教小可怜非常喜欢喝奶茶,特别是KOI的奶茶。

已知小可怜可能出现在 $N$ 个教室,编号从 $1$ 到 $N$ ,这些教室之间有 $N-1$ 条路,且每间教室之间互相连通。

超级NICE的OLD FRIEND知道小可怜每天可能沿着 $K$ 条路线,第 $i$ 条路线从 $s_i$ 到 $t_i$ 去拿奶茶。每天早上,他会沿着这 $K$ 条路线走一遍,在走第 $i$ 条路线时,他会在沿途的每一个教室多放一杯奶茶。小可怜由于要赶早八来不及了,她决定只去一间教室,那么她最多能拿到多少杯呢?

助教小可怜最近写编译器遇到了大麻烦,所以这个任务就留给了你。

输入格式

第一行有两个数字,为 $N$ 和 $K$

第 $2$ 到 $N$ 行,每行有两个数字 $u$ 和 $v$ ,表示教室 $u$ 和 $v$ 之间直接连通

第 $N+1$ 到 $N+K$ 行描述 $K$ 条路线,每行有两个数字 $s_i$ 和 $t_i$

输出格式

输出为一行,即小可怜只去一间教室最多能拿到多少杯奶茶

样例输入

text 5 10 3 4 1 5 4 2 5 4 5 4 5 4 3 5 4 3 4 3 1 3 3 5 5 4 1 5 3 4

样例输出

text 9

数据范围

对于40%的数据, $1\leq N\leq 1,000$, $1\leq K\leq10,000$

对于100%的数据, $1\leq N\leq 100,000$ , $1\leq K \leq 500,000$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!