Постановка задачи Вам дано дерево с N узлами с корнем в 1. Каждый из N узлов имеет некоторое специальное число Se, связанное с ним.Каждый узел также имеет определенную силу.Мощность каждого узла дерева определяется как количество тяжелых узлов в поддереве узла (включая этот узел).Тяжелый узел - это узел, чья сумма делителей его специального числа кратна 3. Вам задается Q запросов
Существует два типа запросов:
- Тип 1:Обновите специальный номер узла.
- Тип 2: укажите мощность определенного узла.
Формат ввода
Первая строка: дваРазделенные пробелом целые числа N и Q, обозначающие количество узлов в дереве и количество запросов соответственно. Каждая из следующих N-1 строк: два разделенных пробелом целых числа U и V, обозначающие ребро между ними.Следующая строка: N разделенных пробелом целых чисел, i из которых обозначает специальное число, относящееся к узлу i.Первое целое число в следующих Q строках - T (тип запроса).если T равно 1, за ним следуют 2 целых числа X, а Y, обозначающий специальное число S узла X, должно быть обновлено до Y, если T равно 2, за ним следует одно целое число X
Формат вывода
Для каждого запроса типа 2 выведите мощность данного узла X. Ответ на каждый запрос должен начинаться с новой строки
Объяснение моей постановки задачи По сути, у нас есть дерево с пронумерованными узлами (Si).Некоторые из этих узлов предположительно имеют дочерние элементы (поскольку это дерево).
Вопрос, который задают, заключается в том, чтобы найти «мощность» узла, где мощность определяется как число «тяжелых узлов» вэто дети.
«Тяжелый узел» определяется как узел, у которого сумма Si делителей для Si кратна 3.
Существует куча информации, которую нам нужно вычислитьздесь:
- Для данного узла нам нужно получить все его дочерние узлы
- Для каждого дочернего узла нам нужно найти делители для номера этого узла
- Нам нужно сложить делители и определить, является ли оно кратным 3
для заданного входного значения и выходов, например
для входного образца
5 5
1 2
1 3
3 4
3 5
16 8 17 3 18
2 1
2 3
1 3 7
2 1
2 3
пример вывода
3
2
2
1
Код, который я пробовал
function BinarySearchTree() {
this.root = null;
}
BinarySearchTree.prototype.insertNode = function (val) {
var node = {
data : val,
left : null,
right : null
};
var currentNode;
if (!this.root) {
this.root = node;
} else {
currentNode = this.root;
while (currentNode) {
if (val < currentNode.data) {
if (!currentNode.left) {
currentNode.left = node;
break;
} else {
currentNode = currentNode.left;
}
} else if (val > currentNode.data) {
if (!currentNode.right) {
currentNode.right = node;
break;
} else {
currentNode = currentNode.right;
}
} else {
break;
}
}
}
};
var BST = new BinarySearchTree();
BST.insertNode(16);
BST.insertNode(8);
BST.insertNode(17);
BST.insertNode(3);
BST.insertNode(18);
console.log(BST);
мой вывод
BinarySearchTree {
root:
{ data: 16,
left: { data: 8, left: [Object], right: null },
right: { data: 17, left: null, right: [Object] } } }
Теперь я хочу передатьэти данные в массиве, как [16,8,17,3,18]
и хотят найти делители каждого узла и должны проверить, еслиее делители делятся на 3 или нет.Как это сделать?
Это правильный путь?