Submission #1306897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306897		Double_Slash	Mergers (JOI19_mergers)	C++20	100 / 100	412 ms	49660 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

int n, k, s[500001], sum[500001], f[500001], sz[500001], ans = 1;
basic_string<int> adj[500001];

int dfs(int i, int p = 0) {
    int deg = 0;
    for (int j: adj[i]) {
        if (j == p) continue;
        int d = dfs(j, i);
        deg += sz[j] ? d : 1;
        sz[i] += sz[j];
    }
    ans += not sz[i] and deg == (i == 1);
    return deg;
}

int main() {
    cin >> n >> k;
    for (int i = n; --i;) {
        int a, b;
        cin >> a >> b;
        adj[a] += b;
        adj[b] += a;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        ++f[s[i]];
    }
    for (int i = 1; i <= n; ++i) {
        if (--f[s[i]]) sum[s[i]] += sz[i] = rand();
        else sz[i] = -sum[s[i]];
    }
    dfs(1);
    cout << ans / 2;
}

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