제출 #248665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
248665		fivefourthreeone	Mergers (JOI19_mergers)	C++17	100 / 100	1465 ms	167928 KiB

mergers

#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 998244353;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 500001;
vector<int> adj[mxN];
int n, k;
int state[mxN];
int high[mxN];
int depth[mxN];
int val[mxN];
int par[mxN];
bool flag[mxN];
int best[mxN];
int ans = 0;
int cnt =0;
ttgl edges[mxN];
int dsu[mxN];
int sz[mxN];
map<int, int> mp[mxN];
int find(int a){return dsu[a]==a ? a : dsu[a] = find(dsu[a]);}
void merge(int a, int b) {
    a = find(a);b = find(b);
    if(sz[b]<sz[a]) swap(a, b);
    dsu[a] = b;
    sz[b]+=sz[a];
}
void comb(int u, int v) {
    if(mp[u].size()<mp[v].size()) {
        swap(mp[u], mp[v]);   
    }
    for(auto p: mp[v]) {
        mp[u][p.first]+=p.second;
        if(mp[u][p.first]==state[p.first]) {
            mp[u].erase(p.first);
        }
    }
}
void dfs(int u, int p) {
    par[u] = p;
    mp[u][val[u]]++;
    for(int v: adj[u]) {
        if(v==p)continue;
        depth[v] =depth[u]+1;
        dfs(v, u);
        comb(u, v);
    }
    for(auto p: mp[u]) {
        if(mp[u][p.first]==state[p.first]) {
            mp[u].erase(p.first);
        }
    }
    if(!mp[u].empty()) {
        //cout<<u<<"\n";
        merge(val[u], val[p]);
    }
}
int deg[mxN];
int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>k;
    int a, b;
    owo(i, 0, n-1) {
        cin>>a>>b;
        a--; b--;
        edges[i] = {a, b};
        adj[a].senpai(b);
        adj[b].senpai(a);
    }
    owo(i, 0, n) {
        cin>>a;
        a--;
        val[i] = a;
        state[a]++;
    }
    owo(i, 0, k) {
        dsu[i] = i;
        sz[i] = 1;
        //cout<<state[i]<<"\n";
    }
    dfs(0, 0);
    for(auto p: edges) {
        if(find(val[p.first])!=find(val[p.second])) {
            deg[find(val[p.first])]++;
            deg[find(val[p.second])]++;
        }
    }
    owo(i, 0, k){
        if(deg[i]==1) ans++;
    }
    //cout<<ans<<"\n";
    cout<<(ans+1)/2<<"\n";
    return 0;
}

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