제출 #716246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
716246		Ahmed57	Mergers (JOI19_mergers)	C++14	0 / 100	55 ms	8964 KiB

mergers

#include <bits/stdc++.h>

using namespace std;
vector<int> adj[200001];
int arr[200001] , cnt[200001];
bool mark[200001];
pair<int,map<int,int>> dfs(int i,int pr){
    map<int,int> mp;
    pair<int,map<int,int>> p1;
    int bad = 0;
    mp[arr[i]]++;
    if(cnt[arr[i]]!=1)bad++;
    for(auto j:adj[i]){
        if(j!=pr){
            p1 = dfs(j,i);
            bad+=p1.first;
            if(p1.second.size()>mp.size())swap(mp,p1.second);
            for(auto k:p1.second){
                if(mp[k.first]!=0)bad--;
                mp[k.first]+=k.second;
                if(mp[k.second]==cnt[k.first]&&k.second!=cnt[k.first])bad--;
            }
        }
    }
    if(bad==0){
        mark[i] = 1;
    }
    return {bad,mp};
}
int calc(int i,int pr){
    long long sum = 0;
    long long ma = 0;
    for(auto j:adj[i]){
        if(j==pr)continue;
        long long val = calc(j,i);
        sum+=val;
        ma = max(ma,val);
    }
    if(ma>sum-ma){
        return ma;
    }else{
        return (sum/2)+(mark[i]||sum%2);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
        cnt[arr[i]]++;
    }
    pair<int,map<int,int>> nothing = dfs(1,0);
    cout<<calc(1,0)-1<<"\n";
}

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