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

    ID: 6055 传统题 1000ms 128MiB 尝试: 29 已通过: 19 难度: 3 上传者: 标签>最近公共祖先 LCA树链剖分差分普及+/提高−

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

【题意】

给定一棵有 NN 个点的树,一开始所有节点的权值都为 00

KK 次操作,每次指定两个点 s,ts,t,将 sstt 路径上所有点的权值都加一。

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

【输入格式】

第一行输入两个整数 N KN\ K2N5×104,1K1052 \le N \le 5 \times 10^4,1 \le K \le 10^5)。

接下来 N1N-1 行每行输入两个整数 x yx\ yxyx \ne y),表示 xxyy 之间的一条无向边。

接下来 KK 行每行两个整数 s ts\ t,描述一条从 sstt 的路径。

【输出格式】

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

【样例输入】

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

【样例输出】

9