HDU6203 ping ping ping

Description

给你一颗以 $0$ 为根的有根树。现在有些节点坏掉了，与周围无法联通。已知 $m$ 对 $(u,v)​$ 无法联通，求最少坏了几个节点。

Solution

对于一对无法联通的节点 $(u,v)$，一般是贪心地删掉 $u, v$ 的 LCA。但如果这条链在之前删除其他链的 LCA 时已经不联通了，那么就可以直接跳过。

所以得到一个做法：求出每对 $(u,v)$ 的 LCA ，按照深度从大到小排序。依次处理。如果当前的链上已经有点被删除了，直接跳过；否则 ans++，将 LCA 打个标记表示已被删除。可以用树链剖分维护。

考虑更简单的做法。因为已经将 LCA 的深度从大到小排过序了，所以每次删除 LCA 可以直接把 LCA 这个子树里的所有点打上标记（加上1）与只打 LCA 一个标记是等价的。这个过程直接用树状数组维护 dfs 序就可以了。

时间复杂度 $O(m \log n)$

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 100010; 

int n, m, tot, dep[N], fa[N][19], dfn[N], siz[N]; 

struct edge {
  int v; edge *next;              
} pool[N * 2], *head[N], *cur = pool;

void addedge(int u, int v) {
  edge *p = cur++, *q = cur++; 
  p->v = v, p->next = head[u], head[u] = p; 
  q->v = u, q->next = head[v], head[v] = q; 
}

void dfs(int u, int pre) {
  siz[u] = 1; dfn[u] = ++tot; 
  for(edge *p = head[u]; p; p = p->next) {
    int v = p->v; if(v == pre) continue ; 
    dep[v] = dep[u] + 1; fa[v][0] = u; 
    dfs(v, u); siz[u] += siz[v]; 
  }
}

struct node {
  int u, v, lca; 
}E[N];

int LCA(int u, int v) {
  if(dep[u] < dep[v]) swap(u, v); 
  for(int i = 16; i >= 0; i--)  
    if(dep[fa[u][i]] >= dep[v]) 
      u = fa[u][i]; 
  if(u == v) return u; 
  for(int i = 16; i >= 0; i--) 
    if(fa[u][i] != fa[v][i]) 
      u = fa[u][i], v = fa[v][i]; 
  return fa[u][0]; 
}

bool cmp(node x, node y) {
  return dep[x.lca] > dep[y.lca]; 
}

int c[N]; 

int lb(int x) {
  return x & (-x); 
}

void add(int x, int d) {
  for(int i = x; i <= n + 1; i += lb(i)) 
    c[i] += d; 
}

int sum(int x) {
  int ret = 0; 
  for(int i = x; i; i -= lb(i))
    ret += c[i]; 
  return ret; 
}

void A(int l, int r) {
  add(l, 1), add(r + 1, -1); 
}

int main() {
  while(scanf("%d", &n) != EOF) {
    n++;
    memset(dep, 0, sizeof(dep)); 
    memset(fa, 0, sizeof(fa)); 
    memset(dfn, 0, sizeof(dfn)); 
    memset(c, 0, sizeof(c)); 
    tot = 0; 
    for(int i = 1; i <= n; i++) 
      head[i] = NULL; 
    cur = pool; 
    for(int i = 1; i < n; i++) {
      int u, v; scanf("%d %d", &u, &v); 
      u++, v++; addedge(u, v); 
    }
    scanf("%d", &m); 
    dfs(1, 0); 
    for(int j = 1; (1 << j) <= n; j++) 
      for(int i = 1; i <= n; i++) 
        fa[i][j] = fa[fa[i][j - 1]][j - 1]; 
    for(int i = 1; i <= m; i++) {
      int u, v; scanf("%d %d", &u, &v); u++, v++; 
      E[i].u = u, E[i].v = v, E[i].lca = LCA(u, v); 
    } sort(E + 1, E + m + 1, cmp);
    int ans = 0; 
    for(int i = 1; i <= m; i++) {
      int u = E[i].u, v = E[i].v, lca = E[i].lca; 
      if(!sum(dfn[u]) && !sum(dfn[v])) 
        ans++, A(dfn[lca], dfn[lca] + siz[lca] - 1); 
    } printf("%d\n", ans); 
  }
  return 0; 
}