{"problem":{"name":"J. Чокнутый профессор-2","description":{"content":"Быстро летит время год за годом. И снова, как и каждый год, профессор МИСиСа задал группе студентов подготовить курсовую работу на тему: \"Расчет воздухонагревателя доменной печи\". В назначенный день и","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10144J"},"statements":[{"statement_type":"Markdown","content":"Быстро летит время год за годом. И снова, как и каждый год, профессор МИСиСа задал группе студентов подготовить курсовую работу на тему: \"Расчет воздухонагревателя доменной печи\". В назначенный день и час все студенты принесли курсовые работы и дружно скопировали их на компьютер профессора.\n\nПрофессору стало интересно: а какова вероятность того, что студенты списали работы друг у друга? Для того чтобы это проверить, он решил просто сравнить названия папок и файлов в своей файловой системе. Файловая система профессора представляет из себя корневое дерево (то есть дерево с выделенным корнем), на каждой вершине которого написано некоторое целое число (название). Более того, как и в обычной файловой системе, внутри папки не может содержаться двух файлов (папок) с одинаковыми названиями.\n\nПрофессор считает, что каждая пара изоморфных корневых поддеревьев в его файловой системе является кандидатом на списанные курсовые. Для начала ему интересно посчитать, сколько таких пар существует. Помогите ему в этом.\n\nНапомним, что корневое поддерево состоит из заданной вершины-корня и всех ее потомков.\n\nДва корневых поддерева являются изоморфными, если каждой вершине первого поддерева можно однозначно поставить в соответствие ровно одну вершину второго поддерева таким образом, чтобы: \n\n(a) каждая вершина второго поддерева соответствовала ровно одной вершине первого поддерева, причем с тем же самым значением;\n\n(б) корень первого поддерева соответствовал корню второго поддерева; \n\n(в) две вершины первого поддерева были соединены ребром тогда и только тогда, когда ребром соединены соответствующие вершины второго поддерева.\n\nВ первой строке дано целое число n – количество вершин в дереве, 2 ≤ n ≤ 105. \n\nВ следующих (n - 1) строках через пробел даны по два целых числа ui и vi – номера вершин, которые соединяет i-тое ребро дерева, 1 ≤ ui,  vi ≤ n, ui ≠ vi, 1 ≤ i ≤ n. \n\nВ последней строке через пробел даны n целых чисел ci – значения вершин дерева, 1 ≤ ci ≤ 109, 1 ≤ i ≤ n. \n\nКорень дерева находится в вершине номер 1.\n\nВыведите единственное число – количество пар изоморфных корневых поддеревьев.\n\n## Входные Данные\n\nВ первой строке дано целое число n – количество вершин в дереве, 2 ≤ n ≤ 105. В следующих (n - 1) строках через пробел даны по два целых числа ui и vi – номера вершин, которые соединяет i-тое ребро дерева, 1 ≤ ui,  vi ≤ n, ui ≠ vi, 1 ≤ i ≤ n. В последней строке через пробел даны n целых чисел ci – значения вершин дерева, 1 ≤ ci ≤ 109, 1 ≤ i ≤ n. Корень дерева находится в вершине номер 1.\n\n## Выходные Данные\n\nВыведите единственное число – количество пар изоморфных корневых поддеревьев.\n\n## Примеры\n\nВходные данные41 21 33 41 2 3 2Выходные данные1Входные данные61 21 31 43 54 61 2 3 4 2 2Выходные данные3\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ m \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 20 $, $ 1 \\leq m \\leq 10000 $.  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n - 1 $.  \n\n**Constraints**  \nThe Wiener index of $ T $, defined as  \n$$\nW(T) = \\sum_{\\{u,v\\} \\subseteq V, u \\ne v} \\text{dist}_T(u,v),\n$$  \nmust satisfy $ W(T) = m $, where $ \\text{dist}_T(u,v) $ is the number of edges in the unique path between $ u $ and $ v $ in $ T $.  \n\n**Objective**  \nDetermine whether there exists a tree $ T $ on $ n $ vertices such that $ W(T) = m $.  \nIf yes, output any such tree via its $ n-1 $ edges; otherwise, output \"NO\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10144J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}