H. A11*【树上点差分】树上路径修改和点查询1[USACO15DEC] Max Flow P

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

给定一棵有 $N$ 个点的树，一开始所有节点的权值都为 $0$ 。

有 $K$ 次操作，每次指定两个点 $s,t$ ，将 $s$ 到 $t$ 路径上所有点的权值都加一。

请输出 $K$ 次操作完毕后权值最大的那个点的权值。

第一行输入两个整数 $N\ K$ （ $2 \le N \le 5 \times 10^4,1 \le K \le 10^5$ ）。

接下来 $N-1$ 行每行输入两个整数 $x\ y$ （ $x \ne y$ ），表示 $x$ 和 $y$ 之间的一条无向边。

接下来 $K$ 行每行两个整数 $s\ t$ ，描述一条从 $s$ 到 $t$ 的路径。

一个整数，表示树上点的最大权值。