A49363.树上差分
入门
官方
通过率:0%
时间限制:3.00s
内存限制:256MB
题目描述
一颗有 n 个节点的树,每个点都有权值,一开始每个点的权值都为 0.
现在有 m 次操作。
每次操作会让 a→b 的直接路径上所有点权 +1。
问 m 次操作完后,所有点权中最大的是多少?
输入格式
第一行 n 和 m。
接下来 n−1 行,每行两个整数 u,v ,表示树上的一条边。
接下来 m 行,每行两个整数 a,b , 表示对 a→b 的直接路径上所有点权 +1。
输出格式
输出所有点中最大的点权值。
输入输出样例
输入#1
5 3 1 2 1 3 1 4 4 5 2 5 2 4 2 4
输出#1
3
说明/提示
对于 100% 的数据,保证 1≤n,m≤106,1≤a,b≤n,且给出的关系一定是一棵树。
注:本题数据量较大,建议使用较快的读入方式。