#O1059. 路径覆盖计数

路径覆盖计数

题目描述

给定一棵 nn 个点的树,再给出 mm 条树上的路径(用两个端点表示)。对每条边,求它被多少条路径经过。请按输入顺序输出每条边的答案。

题目类型

树上差分、LCA

输入格式

第一行两个整数 n,mn, m。

接下来 n−1n-1 行,每行两个整数 u,vu, v,表示第 ii 条边(ii 从 11 开始)。

接下来 mm 行,每行两个整数 u,vu, v,表示一条路径。

输出格式

共 n−1n-1 行,每行一个整数,依次表示每条边被经过的次数(按输入顺序)。

样例 #1

样例输入 #1

3 2
1 2
2 3
1 3
2 3

样例输出 #1

1
2

数据规模与约定

数据范围 说明
1≤n,m≤1051 \le n, m \le 10^5 点数与路径数
  • 对每个路径令 cu++,cv++,clca−=2c_u{+}{+}, c_v{+}{+}, c_{\mathrm{lca}}{-}{=}2,自底向上求和,边 (pu,u)(p_u, u) 的答案即 uu 的子树和。