Submission #1177604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177604		chikien2009	Mergers (JOI19_mergers)	C++20	0 / 100	27 ms	16060 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, k, a, b, c[500000], l[500000], r[500000];
vector<int> g[500000];

inline void DFS1(int node, int par)
{
    if (l[c[node]] == -1)
    {
        l[c[node]] = a;
    }
    a++;
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS1(i, node);
        }
    }
    r[c[node]] = a - 1;
}

inline pair<int, pair<int, int>> DFS2(int node, int par)
{
    pair<int, pair<int ,int>> p;
    int num, high = r[c[node]], low = l[c[node]], sp = a;
    a++;
    for (auto & i : g[node])
    {
        if (i != par)
        {
            p = DFS2(i, node);
            low = min(low, p.second.first);
            high = max(high, p.second.second);
            num += p.first;
        }
    }
    if (low == sp && high == a - 1)
    {
        if (node == 0)
        {
            b += (num == 1);
        }
        else
        {
            b += (num == 0);
            num = 1;
        }
    }
    return {num, {low, high}};
}

int main()
{
    setup();

    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> c[i];
        c[i]--;
        l[c[i]] = -1;
    }
    a = b = 0;
    DFS1(0, 0);
    a = 0;
    DFS2(0, 0);
    cout << (b + 1) / 2;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30