#O1059. 路径覆盖计数
路径覆盖计数
题目描述
给定一棵 个点的树,再给出 条树上的路径(用两个端点表示)。对每条边,求它被多少条路径经过。请按输入顺序输出每条边的答案。
题目类型
树上差分、LCA
输入格式
第一行两个整数 。
接下来 行,每行两个整数 ,表示第 条边( 从 开始)。
接下来 行,每行两个整数 ,表示一条路径。
输出格式
共 行,每行一个整数,依次表示每条边被经过的次数(按输入顺序)。
样例 #1
样例输入 #1
3 2
1 2
2 3
1 3
2 3
样例输出 #1
1
2
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 点数与路径数 |
- 对每个路径令 ,自底向上求和,边 的答案即 的子树和。