Вам дано дерево из \(n\) вершин, в котором вершины пронумерованы от \(0\) до \(n-1\). Для каждого \(k\) от \(0\) до \(n\) включительно вам необходимо посчитать количество неупорядоченных пар \((u,v)\), \(u \neq v\), таких, что MEX всех номеров вершин на пути от \(u\) до \(v\) равен \(k\).
MEX последовательности целых чисел равен наименьшему неотрицательному целому числу, которое в ней не встречается.
Выходные данные
Для каждого набора входных данных выведите \(n+1\) целое число: число путей в дереве таких, что MEX всех номеров вершин на нем равен \(k\), для всех \(k\) от \(0\) до \(n\).
Примечание
- В наборе входных данных \(1\):
- Для \(k = 0\) существует только \(1\) путь из \(2\) в \(3\) с \(MEX([2, 3]) = 0\).
- Для \(k = 1\) существует \(2\) пути. Один из \(0\) в \(2\) с \(MEX([0, 2]) = 1\), и из \(0\) в \(3\) с \(MEX([0, 2, 3]) = 1\).
- Для \(k = 2\) существует \(1\) путь из \(0\) в \(1\) с \(MEX([0, 1]) = 2\).
- Для \(k = 3\) существует \(1\) путь из \(1\) в \(2\) с \(MEX([1, 0, 2]) = 3\)
- Для \(k = 4\) существует \(1\) путь из \(1\) в \(3\) с \(MEX([1, 0, 2, 3]) = 4\).
- В наборе входных данных \(2\):
- Для \(k = 0\) не существует таких путей.
- Для \(k = 1\) не существует таких путей.
- Для \(k = 2\) существует \(1\) путь из \(0\) в \(1\) с \(MEX([0, 1]) = 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
0 1
0 2
2 3
2
1 0
|
1 2 1 1 1
0 0 1
|