제출 #684176

#제출 시각아이디문제언어결과실행 시간메모리
684176finn__Railway (BOI17_railway)C++17
36 / 100
173 ms28400 KiB
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<unsigned, unsigned>>> g;
vector<vector<unsigned>> jmp;
vector<unsigned> height, pre, ans;
vector<int> val;

unsigned lift(unsigned u, unsigned h)
{
    unsigned z = 0;
    while (h)
    {
        if (h & 1)
            u = jmp[u][z];
        h >>= 1;
        z++;
    }
    return u;
}

unsigned lca(unsigned u, unsigned v)
{
    if (height[u] < height[v])
        swap(u, v);
    u = lift(u, height[u] - height[v]);
    if (u == v)
        return u;

    for (size_t i = jmp[u].size() - 1; i < jmp[u].size(); i--)
        if (jmp[u][i] != jmp[v][i])
            u = jmp[u][i], v = jmp[v][i];

    return jmp[u][0];
}

unsigned traverse(
    vector<unsigned> &path, unsigned u, unsigned p, unsigned h, unsigned i)
{
    for (unsigned i = 1; i <= path.size(); i <<= 1)
        jmp[u].push_back(path[path.size() - i]);
    height[u] = h;
    path.push_back(u);
    pre[u] = i++;

    for (auto const &[v, j] : g[u])
        if (v != p)
            i = traverse(path, v, u, h + 1, i);

    path.pop_back();
    return i;
}

void calc_ans(unsigned u, unsigned p)
{
    for (auto const &[v, j] : g[u])
    {
        if (v != p)
        {
            calc_ans(v, u);
            ans[j] = val[v];
            val[u] += val[v];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m, k;
    cin >> n >> m >> k;

    g = vector<vector<pair<unsigned, unsigned>>>(n);
    jmp = vector<vector<unsigned>>(n);
    height = vector<unsigned>(n);
    pre = vector<unsigned>(n);
    ans = vector<unsigned>(n - 1);
    val = vector<int>(n, 0);

    for (size_t i = 0; i < n - 1; i++)
    {
        unsigned u, v;
        cin >> u >> v;
        g[u - 1].emplace_back(v - 1, i);
        g[v - 1].emplace_back(u - 1, i);
    }

    vector<unsigned> path;
    assert(traverse(path, 0, -1, 0, 0) == n);

    for (size_t i = 0; i < m; i++)
    {
        size_t s;
        cin >> s;
        vector<pair<unsigned, unsigned>> y(s);
        for (auto &[j, u] : y)
        {
            cin >> u;
            u--;
            j = pre[u];
        }
        sort(y.begin(), y.end());
        y.resize(unique(y.begin(), y.end()) - y.begin());

        for (size_t j = 0; j < y.size(); j++)
        {
            val[y[j].second]++;
            val[y[(j + 1) % y.size()].second]++;
            val[lca(y[j].second, y[(j + 1) % y.size()].second)] -= 2;
        }
    }

    calc_ans(0, -1);

    unsigned c = 0;
    for (unsigned const &x : ans)
        c += (x >= 2 * k);
    cout << c << '\n';
    for (size_t i = 0; i < n - 1; i++)
        if (ans[i] >= 2 * k)
            cout << i + 1 << ' ';
    cout << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...