A49363.树上差分

入门

官方

通过率:0%

时间限制:3.00s

内存限制:256MB

题目描述

一颗有 nn 个节点的树,每个点都有权值,一开始每个点的权值都为 00.

现在有 mm 次操作。

每次操作会让 aba \to b 的直接路径上所有点权 +1+1

mm 次操作完后,所有点权中最大的是多少?

输入格式

第一行 nnmm

接下来 n1n-1 行,每行两个整数 u,vu,v ,表示树上的一条边。

接下来 mm 行,每行两个整数 a,ba,b , 表示对 aba \to b 的直接路径上所有点权 +1+1

输出格式

输出所有点中最大的点权值。

输入输出样例

  • 输入#1

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

    输出#1

    3

说明/提示

对于 100%100\% 的数据,保证 1n,m1061 \le n,m \le 10^61a,bn1 \leq a,b\leq n,且给出的关系一定是一棵树。

注:本题数据量较大,建议使用较快的读入方式。

首页