问题 M: 简单的基环树
内存限制:1024 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:95
解决:48
题目描述
有 $n$ 个节点与 $n$ 条边的无向连通图,就称为基环树,也就是说,基环树是在一颗树上新增了一条边,使得其形成一个环.
现在给出一个形态最简单的树:一条链
即对于 $ \forall i \in [1,n-1] $ , 有一条边连接 $i$ 与 $i+1$
现在再新增一条连接 $x$ 与 $y$ 的边,我们便得到一个基环树
设 $f(k)$ 为满足 $i$ 到 $j$ 在基环树上的最短距离恰好为 $k$ 的且 $i<j$ 点对$(i,j) $ 数目
请你求出$f(k) \ \ (k=1,2,...,n-1)$ 的值
现在给出一个形态最简单的树:一条链
即对于 $ \forall i \in [1,n-1] $ , 有一条边连接 $i$ 与 $i+1$
现在再新增一条连接 $x$ 与 $y$ 的边,我们便得到一个基环树
设 $f(k)$ 为满足 $i$ 到 $j$ 在基环树上的最短距离恰好为 $k$ 的且 $i<j$ 点对$(i,j) $ 数目
请你求出$f(k) \ \ (k=1,2,...,n-1)$ 的值
输入
输入共一行,输入三个整数 $n,x,y$
$ (3 \leq n \leq 2 \times 10^3)$
$ (1 \leq x,y \leq n,\ x+1 < y)$
$ (3 \leq n \leq 2 \times 10^3)$
$ (1 \leq x,y \leq n,\ x+1 < y)$
输出
输出 $n-1$ 行,每行一个整数
第 $i$ 行代表 $f(i)$ 的值
第 $i$ 行代表 $f(i)$ 的值
样例输入 复制
5 2 4
样例输出 复制
5
4
1
0
提示
样例解释:
有五对$(i,j)(1≤i<j≤n)$使顶点i和顶点j之间的最短距离是1:(1,2),(2,3),(2,4),(3,4),(4,5)。
有四对$(i,j)(1≤i<j≤n)$使顶点i和顶点j之间的最短距离是2:(1,3),(1,4),(2,5),(3,5)。
有一对$(i,j)(1≤i<j≤n)$,使得顶点i和顶点j之间的最短距离是3:(1,5)。
不存在点对$(i,j)(1≤i<j≤n)$使得顶点i和顶点j之间的最短距离是4。