Понять что именно, не сложно)

Если лежит на пути то 1)

Сумма количеств по всем k

Хм

Берешь, подвешиваешь дерево за вершину, спускаешься, возвращаешь сеты пар

Потом поднимаясь в вершину, меджишь сеты, проверяя, чтобы у тебя не было даблов

Если дабл попадание - взаимное уничтожение

Ответ по ребру - количество элементов, возвращенных в сете из поддерева

За счет аккуратного мерджа (мерджим к самому большому сету), ассимптотика nlog^2

А если будешь юзать unordered, то nlog

Понял, спасибо!

Можно проще. Давай просто для каждой пары (ak, bk) прибавим 1 ко всем ребрам на пути, если мы научимся это делать быстро, то мы решим задачу. Подвесим граф. Чтобы прибавить 1 к пути от a до b давай найдем их общего предка (LCA) p и прибавим 1 на пути от a до p и на пути от b до p. Но тут уже просто, давай заведем массив, назовем его kek, чтобы обработать путь [a, p] мы сделаем kek[a]++, kek[p]--. Тогда как нетрудно понять для ребра (u, v) (u предок v) ответом будет что-то типа -kek[u] + ∑kek[s], где сумма берется по всем вершинам в поддереве v. Как-то так

Красиво, спасибо!

Можно даже прибавить 1 на пути от a до корня, 1 на пути от b до корня и вычесть 2 на пути от a до p, так, мне кажется, будет удобнее

да, так тоже можно

на самом деле это и происходит

а, точно

Ага, найти lca проще, удачи)

Сколько ты будешь писать lca с нуля и мердж сэтов?

Думаю отношение порядка 10:1