Submission #207632

#	Time	Username	Problem	Language	Result	Execution time	Memory
207632		nvmdava	Mergers (JOI19_mergers)	C++17	100 / 100	1202 ms	149852 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 500005
#define MOD 1000000007
#define INF 0x3f3f3f3f

int col[N];
int cnt[N];
int dsu[N];
vector<pair<int, int> > e;
vector<int> adj[N];

int find(int x){
    return x == dsu[x] ? x : dsu[x] = find(dsu[x]);
}

void merge(int v, int u){
    v = find(v);
    u = find(u);
    dsu[v] = u;
}

map<int, int> in[N];

void dfs(int v, int p){
    if(cnt[col[v]] != 1)
        in[v][col[v]] = 1;
    for(auto& x : adj[v]){
        if(x == p) continue;
        dfs(x, v);
        if(in[x].size() > in[v].size())
            swap(in[x], in[v]);
    }
    for(auto& x : adj[v]){
        if(x == p) continue;
        for(auto& y : in[x])
            if( (in[v][y.ff] += y.ss) == cnt[y.ff])
                in[v].erase(y.ff);
    }
    if(!in[v].empty())
        merge(col[v], col[p]);
}

int deg[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= k; ++i)
        dsu[i] = i;
    for(int a, b, i = 1; i < n; ++i){
        cin>>a>>b;
        e.push_back({a, b});
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for(int i = 1; i <= n; ++i){
        cin>>col[i];
        ++cnt[col[i]];
    }

    dfs(1, 0);
    for(int i = 1; i <= n; ++i)
        col[i] = find(col[i]);
    
    for(auto& x : e){
        x.ff = col[x.ff];
        x.ss = col[x.ss];
        if(x.ff != x.ss){
            ++deg[x.ff];
            ++deg[x.ss];
        }
    }
    int ans = 0;
    for(int i = 1; i <= k; ++i)
        if(deg[i] == 1)
            ++ans;
    cout<<(ans + 1) / 2;
}

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