LCA

kitty.cpp

#include <iostream>
#include <cstring>
#include <algorithm>
#include <iterator>
#include <vector>
#include <queue>

//  TODO create tree as an array
auto build_tree(std::size_t n) {
    std::vector<int> tree(n);
    for(int vertex1 = 0, vertex2 = 0; n--;) {
        std::cin >> vertex1 >> vertex2;
        tree[vertex2] = vertex1;
    }

    return tree;
}

//  TODO find all pair combinations in a set
template<typename ForwardIter>
auto make_pairs(ForwardIter first, ForwardIter last) {
    std::vector<std::pair<int,int>> pairs;

    for (auto iter = first; iter != last; ++iter)
        for(auto inner_iter = iter; inner_iter != last; ++inner_iter)
            pairs.push_back({*iter, *inner_iter});

    return pairs;   // RVO
}

int fillHeight(const std::vector<int> &p, int node, std::vector<bool> &visited,
               std::vector<int> &height)
{
    if (p[node] == -1) {
        visited[node] = true;
        return 0;
    }

    if (visited[node])
        return height[node];

    visited[node] = true;

    height[node] = 1 + fillHeight(p, p[node],
                                  visited, height);

    return height[node];
}

int findHeight(const std::vector<int> &parent)
{
    int ma = 0;
    std::vector<bool> visited(parent.size());
    std::vector<int> height(parent.size());

    for (int i = 0; i < parent.size(); ++i) {
        for (int j = i; parent[j] != -1 || visited[i]; j = parent[j]) {
            ++height[i];
            ma = std::max(ma, height[i]);
        }
    }

    return ma;
}

std::size_t lca_len(std::vector<int> &tree, int node1, int node2) {

}

int main() {
    std::size_t n, q;
    std::cin >> n >> q;

    auto tree = build_tree(n);

    for (std::size_t k = 0; q--; ) {
        std::cin >> k;
        std::vector<int> data;
        std::copy_n(std::istream_iterator<int>(std::cin), k, std::back_inserter(data));
        auto pairs = make_pairs(data.begin(), data.end());

        long result = 0;
        for(auto &&pair : pairs) {
            result += pair.first * pair.second * lca_len(tree, pair.first, pair.second);
        }
    }

    return 0;
}