제출 #1212209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1212209		minhpk	Mergers (JOI19_mergers)	C++20	100 / 100	510 ms	102960 KiB

mergers

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
vector <int> z[1000005];
int type[1000005];
int limit[1000005];
int cur[1000005];

int sta[1000005];
int fin[1000005];
int rev[1000005];
int tour;



int child[1000005];
int big[1000005];
int mark[1000005];
int bag1,bag2;
int max1=0;
void dfs(int i,int par){
    tour++;
    sta[i]=tour;
    rev[tour]=i;

    child[i]=1;
    big[i]=-1;
    for (auto p:z[i]){
         if (p==par){
             continue;
         }
         dfs(p,i);
         child[i]+=child[p];
         if (big[i]==-1 || child[big[i]]<child[p]){
              big[i]=p;
         }
    }

    fin[i]=tour;
}

void dfs1(int i,int par,bool keep){
    int num=0;
    for (auto p:z[i]){
         if (p!=par && p!=big[i]){
             dfs1(p,i,0);
             num+=mark[p];
         }
    }
    if (big[i]!=-1){
        dfs1(big[i],i,1);
        num+=mark[big[i]];
    }

    for (auto p:z[i]){
         if (p==par){
             continue;
         }
         if (p==big[i]){
             continue;
         }
         for (int j=sta[p];j<=fin[p];j++){
              int x=rev[j];
              x=type[x];
              if (cur[x]==0){
                  bag2++;
              }
              cur[x]++;
              if (cur[x]==limit[x]){
                  bag2--;
                  bag1++;
              }
         }
    }
    int x=type[i];
    if (cur[x]==0){
        bag2++;
    }
    cur[x]++;
    if (cur[x]==limit[x]){
        bag2--;
        bag1++;
    }
    mark[i]=num;
    if (bag1 && !bag2 ){
        if (i==1){
            max1+=(num==1);
        }else{
            max1+=(num==0);
        }
        mark[i]=1;
    }
    //  cout << i << " " << bag1 << " " << bag2 << "\n";
    if (!keep){
        for (int j=sta[i];j<=fin[i];j++){
              x=rev[j];
              x=type[x];
              if (cur[x]==limit[x]){
                  bag2++;
                  bag1--;
              }
              cur[x]--;
              if (cur[x]==0){
                  bag2--;
              }
        }
    }
}

signed main()
{
  //  freopen("test.txt", "r", stdin);
  //  freopen("o2.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    for (int i=1;i<=a;i++){
        cin >> type[i];
        limit[type[i]]++;
    }
    dfs(1,0);
    dfs1(1,0,1);
    cout << (max1+1)/2 << "\n";
    return 0;
}

/*
 cccacaca
*/



/*
freopen("test.txt", "r", stdin);
    freopen("o2.out", "w", stdout);
*/

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