CF757F Team Rocket Rises Again

---

Description

一个 $n$ 个点 $m$ 条边的无向图，给出起点 $S$ 。求删除掉一个不是 $S$ 的点后最多能改变多少个点到 $S$ 的最短路。输出这个最大值。

$n \leq 200000, m \leq \min(\frac{n(n-1)}{2},300000)$

Solution

在飞机上写的题解 2333

定义 $d_u$ 是 $S$ 到 $u$ 的最短路；最短路 DAG 为所有有向边 $(u,v)$ 满足 $d_u+w(u,v)=d_v$ 组成的 DAG .

那么显然删这个 DAG 上的点才是对答案有贡献的。

考虑如何求出删完一个点会使得有多少个点的最短路有改变。

把这个 DAG 的支配树建出来然后对于一个点它在支配树上的子树大小就是答案。

注：支配树是啥？

在一个有向图中有一个节点是 $S$ ；对于节点 $u$ 从 $S$ 到 $u$ 上的路径必到的点称之为 $u$ 的支配点

对于每一个 $u$ ，从离他最近的一个点向他连一条边。这些边组成的便是原图的支配树。其中 $S$ 为根节点

对于一个 DAG 如何建出他的支配树？即对于一个点怎么求出离他最近的支配点？

可以考虑用拓扑排序的顺序更新。对于节点 $u$ ，它的所有前驱在支配树上的 LCA便是它在支配树上的父亲；即离他最近的支配点。

这个过程需要维护的就是 加点 和 维护 LCA 。可以用倍增用 $O(n \log n)$ 的时间复杂度解决

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long // don't think I use int ! 
const int N = 300300; 
const int INF = (int)4e18; 
int n, m, S, dis[N], U[N], V[N], W[N], ind[N], fa[N][25], dep[N], siz[N]; 
vector <int> g[N]; 
struct edge {
  int v, w; edge *next; 
} *h1[N], *h2[N], *h3[N], pool[N * 6], *cur = pool; 
inline void add1(int u, int v, int w) {
  edge *p = cur++; p->w = w; 
  p->v = v, p->next = h1[u], h1[u] = p; 
}
inline void add2(int u, int v) {
  edge *p = cur++;
  p->v = v, p->next = h2[u], h2[u] = p; 
}
inline void add3(int u, int v) {
  edge *p = cur++;
  p->v = v, p->next = h3[u], h3[u] = p; 
}
inline void add(int x, int f) {
  fa[x][0] = f;
  for(int i = 1; i <= 20; i++)
    fa[x][i] = fa[fa[x][i - 1]][i - 1]; 
  dep[x] = dep[f] + 1; 
}
inline int LCA(int u, int v) {
  if(dep[u] < dep[v]) swap(u, v); 
  for(int i = 20; i >= 0; i--)
    if(dep[fa[u][i]] >= dep[v] && fa[u][i])
      u = fa[u][i]; 
  if(u == v) return u; 
  for(int i = 20; i >= 0; i--)
    if(fa[u][i] != fa[v][i])
      u = fa[u][i], v = fa[v][i];
  return fa[u][0]; 
}
struct node {
  int d, id; 
  inline bool operator < (const node &x) const {
    return d > x.d; 
  }
} tmp; 
priority_queue <node> Q; 
inline void dijkstra() {
  for(int i = 1; i <= n; i++)
    dis[i] = INF;
  tmp.id = S, tmp.d = 0; Q.push(tmp); dis[S] = 0; 
  while(!Q.empty()) {
    tmp = Q.top(); Q.pop();
    int u = tmp.id;
    if(dis[u] < tmp.d) continue ; 
    for(edge *p = h1[u]; p; p = p->next) {
      int v = p->v; 
      if(dis[v] > dis[u] + p->w) {
        dis[v] = dis[u] + p->w; 
        tmp.id = v, tmp.d = dis[v];
        Q.push(tmp); 
      }
    }
  }
}
inline void dfs(int u, int pre) {
  siz[u] = 1;
  for(edge *p = h3[u]; p; p = p->next) {
    int v = p->v; if(v == pre) continue ; 
    dfs(v, u); siz[u] += siz[v]; 
  }
}
signed main() {
  scanf("%lld %lld %lld", &n, &m, &S);
  for(int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%lld %lld %lld", &u, &v, &w); 
    U[i] = u, V[i] = v, W[i] = w; 
    add1(u, v, w), add1(v, u, w); 
  }
  dijkstra(); 
  for(int i = 1; i <= m; i++) {
    if(dis[U[i]] == dis[V[i]] + W[i])
      add2(V[i], U[i]), ind[U[i]]++, g[U[i]].push_back(V[i]);
    if(dis[V[i]] == dis[U[i]] + W[i])
      add2(U[i], V[i]), ind[V[i]]++, g[V[i]].push_back(U[i]); 
  } queue <int> Q; Q.push(S); dep[S] = 1; 
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    // printf("%d\n", u); 
    if(g[u].size()) {
      int lca = g[u][0];
      for(int i = 1; i < g[u].size(); i++) {
       // printf("%d\n", g[u][i]); 
        lca = LCA(g[u][i], lca);
      } 
      add(u, lca); add3(lca, u); 
    }
    for(edge *p = h2[u]; p; p = p->next) {
      int v = p->v; ind[v]--;
      if(ind[v] == 0) Q.push(v); 
    }
  } int ans = 0;  
  dfs(S, 0); 
  for(int i = 1; i <= n; i++)
    if(i != S) ans = max(ans, siz[i]); 
  printf("%lld\n", ans); 
  return 0; 
}