Submission #1272833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272833		zNatsumi	Mergers (JOI19_mergers)	C++20	100 / 100	572 ms	121060 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

int n, k, f[N], g[N], leaf, tot;
vector<int> ad[N], vt[N];

int in[N], out[N], timer, up[N][20];
void dfs0(int u, int p){
  in[u] = ++timer;
  for(int i = 1; i <= 18; i++) up[u][i] = up[up[u][i - 1]][i - 1];

  for(auto v : ad[u]) if(v != p){
    up[v][0] = u;
    dfs0(v, u);
  }
  out[u] = timer;
}

bool anc(int u, int v){ return in[u] <= in[v] && out[v] <= out[u]; }

int LCA(int u, int v){
  if(anc(u, v)) return u;
  if(anc(v, u)) return v;
  for(int i = 18; i >= 0; i--)
    if(up[u][i] && !anc(up[u][i], v)) u = up[u][i];
  return up[u][0];
}

void dfs1(int u, int p){
  for(auto v : ad[u]) if(v != p){
    dfs1(v, u);
    f[u] += f[v];
    g[u] += g[v] + (!f[v]);
  }
  if(p != -1 && !f[u]) tot += 1;
}

void dfs2(int u, int p){
  for(auto v : ad[u]) if(v != p){
    dfs2(v, u);
    if(!f[v]) leaf += (!g[v]) + (g[v] + 1 == tot);
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> k;
  for(int i = 1; i < n; i++){
    int u, v; cin >> u >> v;
    ad[u].push_back(v); ad[v].push_back(u);
  }
  for(int i = 1; i <= n; i++){
    int x; cin >> x;
    vt[x].push_back(i); f[i] = 1;
  }
  dfs0(1, -1);
  for(int x = 1; x <= k; x++){
    int p = vt[x][0];
    for(auto i : vt[x]) p = LCA(p, i);
    f[p] -= vt[x].size();
  }
  dfs1(1, -1);
  dfs2(1, -1);
  cout << (leaf + 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