Submission #863484

#	Time	Username	Problem	Language	Result	Execution time	Memory
863484		NeroZein	Mergers (JOI19_mergers)	C++17	0 / 100	50 ms	39048 KiB

mergers

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 5e5 + 5; 

int sz[N]; 
int od, id;
int leaves;
int col[N];
bool bad[N]; 
int in[N], out[N]; 
vector<int> vec[N]; 
vector<int> g[N];

int pre(int v, int p) {
  sz[v] = 1;
  for (int u : g[v]) {
    if (u != p) {
      pre(u, v); 
      sz[v] += sz[u];
    }
  }
  return sz[v];
}

void dfs(int v, int p, bool keep) {
  int big = 0;
  for (int u : g[v]) {
    if (u != p && sz[u] > sz[big]) {
      big = u; 
    }
  }
  for (int u : g[v]) {
    if (u != p && u != big) {
      dfs(u, v, false); 
    }
  }
  if (big) {
    dfs(big, v, true); 
    swap(vec[v], vec[big]); 
  }
  if (--out[col[v]] == 0) {
    od++; 
  }
  if (in[col[v]]++ == 0) {
    id++;
  }
  vec[v].push_back(v); 
  for (int u : g[v]) {
    if (u == p || u == big) {
      continue;
    }
    for (int x : vec[u]) {
      if (--out[col[x]] == 0) {
        od++;
      }
      if (in[col[x]]++ == 0) {
        id++; 
      }
      vec[v].push_back(u); 
    }
  }
  if (od == id) {
    bad[v] = true; 
  }
  if (!keep) {
    for (int u : vec[v]) {
      if (out[col[u]]++ == 0) {
        od--;
      }
      if (--in[col[u]] == 0) {
        id--;
      }
    }
  }
}

bool dfs2(int v, int p) {
  bool ret = false;
  for (int u : g[v]) {
    if (u != p) {
      ret |= dfs2(u, v); 
    }
  }
  if (!ret && bad[v]) {
    ret = true;
    leaves++; 
  }
  return ret;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> col[i]; 
    out[col[i]]++;
  }
  pre(1, 1); 
  dfs(1, 1, 1); 
  bad[1] = false;
  dfs2(1, 1); 
  cout << (leaves + 1) / 2 << '\n'; 
  return 0;
}

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