題意：
給你 n 個點， m 條雙向邊，求爆了某個點后，從s出發的最短路距離，會改變最多的數量。
分析：
建出最短路樹（DAG）之后，在最短路樹上跑一下支配樹，找出支配的點。答案就是爆支配點的收益，即為該點支配的 size。上支配樹模板即可。支配樹教程：oi-wiki 板子
支配樹算法用的是 Lengauer-Tarjan，簡單講一下，首先是支配樹里面的定義：
u的半支配點 指的是dfn最小的v(v<u) 滿足v到u存在一條路徑 路徑中所有點dfn 都 > u
兩條定理，對應的是函數 LengauerTarjan 里的寫法：
- u的半支配點是 大于u的所有祖先的半支配點中最小的節點，
- sdom(u) 到 u 路徑中所有節點 v 都滿足 sdom(v) >= sdom(u)，則 idom(u) = sdom(u)
代碼：
#include <bits/stdc++.h>
#define N 200005using namespace std;struct MAP {struct Edge {int x, y, nex;long long d;} edge[N * 5];int len, fir[N];void init(){len = 0;memset(fir, -1, sizeof fir);}void addEdge(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].nex = fir[x]; fir[x] = len; }void addEdge(int x, int y, long long d){len++; edge[len].x=x; edge[len].y=y; edge[len].d=d; edge[len].nex=fir[x]; fir[x]=len;}
};
MAP input;
MAP G, GF;
MAP dfsTree, dfsTreeF;
MAP dominate;queue<int> q;
bool vis[N];
long long dis[N];
int n, m, s;void SPFA()
{memset(vis, 0, sizeof vis);memset(dis, 126, sizeof dis);q.push(s);dis[s] = 0;vis[s] = 1;while (!q.empty()) {int x = q.front();q.pop();vis[x] = 0;for (int k = G.fir[x]; k != -1; k = G.edge[k].nex) {int y = G.edge[k].y;if (dis[y] > dis[x] + G.edge[k].d) {dis[y] = dis[x] + G.edge[k].d;if (!vis[y]) {vis[y] = 1;q.push(y);}}}}
}struct DominatorTree {DominatorTree(){tot = 0;}int id[N], dfn[N], fa[N], tot;int anc[N], sdom[N], mn[N];int in[N];int dp[N][21], dep[N];int idom[N];int dominateSize[N];int Find(int x) {if(x != anc[x]) {int t = anc[x];anc[x] = Find(anc[x]);if(dfn[sdom[mn[x]]] > dfn[sdom[mn[t]]]) {mn[x] = mn[t];}}return anc[x];}void Dfs(int x) {dfn[x] = ++tot;id[tot] = x;for (int k = G.fir[x]; k != -1; k = G.edge[k].nex) {int y = G.edge[k].y;if (!dfn[y]) {Dfs(y);fa[y] = x;dfsTree.addEdge(x, y);}}}void LengauerTarjan() {for(int i = 1; i <= n; i++) {anc[i] = i;sdom[i] = i;mn[i] = i;}for(int i = n; i >= 2; i--) {int x = id[i];if(!x) continue;int pos = i;for(int k = GF.fir[x]; k != -1; k = GF.edge[k].nex) {int y = GF.edge[k].y; // pre// if(!dfn[y]) continue;if(dfn[y] < dfn[x]) {pos = min(pos, dfn[y]);} else {Find(y); // find pos = min(pos, dfn[sdom[mn[y]]]);}}sdom[x] = id[pos];anc[x] = fa[x];dfsTree.addEdge(sdom[x], x);}}int LCA(int x, int y) {if (dep[x] < dep[y]) {swap(x, y);}int deep = dep[x] - dep[y];for (int i = 20; i >= 0; i--) {if (deep >= (1 << i)) {deep -= (1 << i);x = dp[x][i];}}if (x == y) {return x;}for (int i = 20; i >= 0; i--) {if (dp[x][i] != dp[y][i]) {x = dp[x][i];y = dp[y][i];}}return dp[x][0];}void BuildDominate(int x) {int to = dfsTreeF.edge[dfsTreeF.fir[x]].y;for(int k = dfsTreeF.fir[x]; k != -1; k = dfsTreeF.edge[k].nex) {int y = dfsTreeF.edge[k].y;to = LCA(to, y);}idom[x] = to;dep[x] = dep[to] + 1;dp[x][0] = to;dominate.addEdge(to, x);for(int i = 1; i <= 20; i++) dp[x][i] = dp[dp[x][i-1]][i-1];}void TopSort() {for (int x = 1; x <= n; x++) {for(int k = dfsTree.fir[x]; k != -1; k = dfsTree.edge[k].nex) {int y = dfsTree.edge[k].y;in[y] ++;dfsTreeF.addEdge(y, x);}}for(int x = 1; x <= n; x++) {if(!in[x]) {in[x] ++;dfsTree.addEdge(0, x);dfsTreeF.addEdge(x, 0);}}queue<int> q;q.push(0);while(!q.empty()) {int x = q.front();q.pop();for(int k = dfsTree.fir[x]; k != -1; k = dfsTree.edge[k].nex) {int y = dfsTree.edge[k].y;in[y] --;if(in[y] == 0) {q.push(y);BuildDominate(y);}}}}void DfsDominate(int x) {dominateSize[x] = 1;for(int k = dominate.fir[x]; k != -1; k = dominate.edge[k].nex) {int y = dominate.edge[k].y;DfsDominate(y);dominateSize[x] += dominateSize[y];}}void Run(int s) {dfsTree.init();dfsTreeF.init();dominate.init();Dfs(s);LengauerTarjan();TopSort();DfsDominate(s);}} dominatorTree;int main() {cin.tie(0);ios::sync_with_stdio(false);cin >> n >> m >> s;G.init();for (int i = 1; i <= m; i++) {cin >> input.edge[i].x >> input.edge[i].y >> input.edge[i].d;G.addEdge(input.edge[i].x, input.edge[i].y, input.edge[i].d);G.addEdge(input.edge[i].y, input.edge[i].x, input.edge[i].d);}SPFA();G.init();GF.init();for (int i = 1; i <= m; i++) {if (dis[input.edge[i].y] == dis[input.edge[i].x] + input.edge[i].d) {G.addEdge(input.edge[i].x, input.edge[i].y);GF.addEdge(input.edge[i].y, input.edge[i].x); } else if (dis[input.edge[i].x] == dis[input.edge[i].y] + input.edge[i].d) {G.addEdge(input.edge[i].y, input.edge[i].x);GF.addEdge(input.edge[i].x, input.edge[i].y);}}dominatorTree.Run(s);int res = 0;for(int i = 1; i <= n; i++) {if(i == s) continue;res = max(res, dominatorTree.dominateSize[i]);}cout << res << endl;return 0;
}
)
)
