Submission #630988

#	Time	Username	Problem	Language	Result	Execution time	Memory
630988		cadmiumsky	Mergers (JOI19_mergers)	C++14	100 / 100	1351 ms	130368 KiB

mergers

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 5e5 + 5, nbit = 19;

int n, k;
vector<int> g[nmax];

int pin[nmax], pout[nmax], inp = 1;
namespace LCA {
  int p[nmax][nbit];
  void init(int node, int f) {
    pin[node] = inp++;
    p[node][0] = f;
    for(int i = 1; i < nbit; i++)
      p[node][i] = p[p[node][i - 1]][i - 1];
    for(auto x : g[node])
      if(x == f) continue;
      else init(x, node);
    pout[node] = inp++;
  }
  bool isanc(int x, int y) {return pin[x] <= pin[y] && pout[y] <= pout[x]; }
  int lca(int x, int y) {
    if(isanc(x, y)) return x;
    if(isanc(y, x)) return y;
    for(int i = nbit - 1; i >= 0; i--)
      if(!isanc(p[x][i], y))	
	x = p[x][i];
    return p[x][0];
  }
};

vector<int> ofcol[nmax];
int lca[nmax];
int start[nmax], fin[nmax];
int cnt;

vector<int> cuts;
int identify(int node, int f) {
  int sum = start[node] + fin[node];
  for(auto x : g[node]) {
    if(x == f) continue;
    int tmp = identify(x, node);
    if(tmp == 0)
      cuts.push_back(x);
    else
      sum += tmp;
  }
  return sum;
}

int noise_reduction(int node, int f) {
  int sum = 0;
  for(auto x : g[node]) {
    if(x == f) continue;
    sum += noise_reduction(x, node);
  }
  if((sum == 0 && start[node] == 1 && node != f) || (node == f && sum == 1))
    cnt++;
  return !start[node] * sum + start[node];
}

signed main() {
  cin >> n >> k;
  for(int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  LCA::init(1, 1);
  for(int i = 1, x; i <= n; i++) {
    cin >> x;
    ofcol[x].push_back(i); 
  }
  for(int i = 1; i <= k; i++) {
    lca[i] = ofcol[i].back();
    for(auto x : ofcol[i])
      lca[i] = LCA::lca(x, lca[i]);
    for(auto x : ofcol[i])
      start[x]++, 
      fin[lca[i]]--;
  }
  
  identify(1, 1);
  
  cuts.push_back(1);
  for(int i = 1; i <= n; i++)
    start[i] = 0;
  for(auto x : cuts)
    start[x] = 1;
   noise_reduction(1, 1);
   
  cout << (cnt + 1) / 2 << '\n';
}

/**
  De-atâtea nopți aud plouând,
  Aud materia plângând..
  Sînt singur, și mă duce un gând
  Spre locuințele lacustre.

  Și parcă dorm pe scânduri ude,
  În spate mă izbește-un val --
  Tresar prin somn și mi se pare
  Că n-am tras podul de la mal.

  Un gol istoric se întinde,
  Pe-același vremuri mă găsesc..
  Și simt cum de atâta ploaie
  Pilonii grei se prăbușesc.

  De-atâtea nopți aud plouând,
  Tot tresărind, tot așteptând..
  Sînt singur, și mă duce-un gând
  Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/

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