Submission #129917

#	Time	Username	Problem	Language	Result	Execution time	Memory
129917		doowey	Mergers (JOI19_mergers)	C++14	100 / 100	913 ms	82492 KiB

mergers

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)5e5 + 9;

int pi[N];
int fin(int x){
    if(pi[x] == x)
        return x;
    return pi[x]=fin(pi[x]);
}

void unite(int a, int b){
    a=fin(a);
    b=fin(b);
    if(a==b)
        return;
    pi[a] = b;
}

vector<int> T[N];
int dep[N];
int par[N];

void dfs(int u, int pr){
    par[u] = pr;
    for(auto p : T[u]){
        if(p == pr) continue;
        dep[p] = dep[u] + 1;
        dfs(p, u);
    }
}

vector<int> col[N];

void path(int a, int b){
    a = fin(a);
    b = fin(b);
    while(a != b){
        if(dep[a] < dep[b]) swap(a, b);
        unite(a, par[a]);
        a = fin(a);
        b = fin(b);
    }
}

int deg[N];

int main(){
    fastIO;
    int n,k;
    cin >> n >> k;
    int u, v;
    for(int i = 2; i <= n; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    dfs(1, -1);
    int cl;
    for(int i = 1; i <= n; i ++ ){
        cin >> cl;
        col[cl].push_back(i);
    }
    for(int i = 1; i <= n; i ++ )
        pi[i] = i;
    for(int i = 1; i <= k ; i ++ ){
        for(auto p : col[i]){
            path(col[i][0], p);
        }
    }
    for(int i = 1; i <= n; i ++ )
        for(auto p : T[i])
            if(fin(i) != fin(p))
                deg[fin(p)] ++ ;
    int sz = 0;
    for(int i = 1; i <= n; i ++ )
        if(deg[i] == 1)
            sz ++ ;
    cout << (sz + 1) / 2;
    return 0;
}

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