Codeforces Round 157 (Div. 1) |
---|
Закончено |
Маленький Слоник очень любит деревья, а особенно корневые.
У него есть дерево, состоящее из n вершин (вершины пронумерованы от 1 до n), с корнем в вершине с номером 1. В каждой вершине дерева хранится некоторый список чисел, который изначально пуст.
Маленький Слоник хочет выполнить m операций. На i-той операции (1 ≤ i ≤ m) он сначала добавляет число i в списки всех вершин поддерева с корнем в вершине с номером ai, а потом добавляет число i в списки всех вершин поддерева с корнем в вершине bi.
После выполнения всех операций, Маленький Слоник для каждой вершины i хочет посчитать число ci — количество целых чисел j (1 ≤ j ≤ n; j ≠ i) таких, что в списках i-той и j-той вершины есть хотя бы одно общее число.
Помогите Маленькому Слонику, посчитайте числа ci за него.
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 105) — количество вершин дерева и количество операций.
Каждая из следующих n - 1 строк содержит два целых числа, разделенных пробелом, ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi), которые обозначают, что существует ребро между вершинами с номерами ui и vi.
Каждая из следующих m строк содержит два целых числа, разделенных пробелом, ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi), которые обозначают номера вершин в i-той операции.
Гарантируется, что заданный граф являет неориентированным деревом.
В единственной строке выведите n целых чисел через пробел — c1, c2, ..., cn.
5 1
1 2
1 3
3 5
3 4
2 3
0 3 3 3 3
11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8
0 6 7 6 0 2 0 5 4 5 5
Название |
---|