为了做这个题学了一下支配树大概是个什么玩意。一般图支配树被鸽了，只写一下 DAG 上支配树的做法。

考虑一个单源有向图，上的一个点 $u$ 如果存在一个点 $v$ 满足删除 $v$ 后 $u$ 无法从源点到达，那么我们称 $v$ 支配点 $u$ 。

显然，同一个点的支配点很多，设这些点是 $v_1,v_2, \dots ,v_k$ ，同时显然源点也是一个支配点。

• 如果 $a$ 支配 $b$ ，$b$ 支配 $c$ ，那么有 $a$ 支配 $c$ 。证明显然。
• 如果 $a$ 支配 $c$ ，$b$ 也支配 $c$ ，那么 $a,b$ 间一定存在支配关系。如果不存在，那么显然从原点通过 $a,b$ 均可到达 $c$ ，因此这两个点就都不支配 $c$ 了。

所以 $v_1, \dots ,v_k$ 这个支配点集合满足一个全序关系，因此一定可以找到一个“最小”的支配点，使得其他支配点都支配这个点，我们称之为 $\text{Idom}(x)$ 。

于是支配树的定义就是从 $\text{Idom}(x)$ 向 $x$ 连一条边出去，得到的一个树。

在这道题中，建立了最短路图（是个 DAG ）后就成了一个删除一个点，最多可以让多少点不可达的问题，如果建立了支配树，显然答案就是除原树外最大的子树大小。

下面说一下 DAG 怎么建立支配树。我们按照拓扑序从小到大考虑。对于每一个位置，它的父亲就是所有它的前驱在树中位置的 LCA 。因此可以非常方便地建出支配树。

复杂度 $O(n\log n)$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 400006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , s;
int A[MAXN];

vector<pii> G[MAXN];

ll dis[MAXN];
int vis[MAXN];
void dijk( ) {
	memset( dis , 0x3f , sizeof dis );
	dis[s] = 0;
	priority_queue<pair<ll,int>> Q;
	Q.push( mp( 0ll , s ) );
	while( !Q.empty() ) {
		int u = Q.top().se; Q.pop();
		if( vis[u] ) continue;
		vis[u] = 1;
		for( auto t : G[u] ) if( dis[u] + t.se < dis[t.fi] ) {
			int v = t.fi;
			dis[v] = dis[u] + t.se;
			Q.push( mp( -dis[v] , v ) );
		}
	}
}

vi g[MAXN] , rg[MAXN] , Gt[MAXN];
int deg[MAXN];

int J[MAXN][20] , dep[MAXN];
int lca( int u , int v ) {
	if( dep[u] < dep[v] ) swap( u , v );
	if( dep[u] != dep[v] ) 
		per( k , 17 , 0 ) if( dep[J[u][k]] >= dep[v] ) u = J[u][k];
	if( u == v ) return u;
	per( k , 17 , 0 ) if( J[u][k] != J[v][k] ) u = J[u][k] , v = J[v][k];
	return J[u][0];
}

int sz[MAXN];
int as;
void dfs( int u ) {
	sz[u] = 1;
	for( int v : Gt[u] ) dfs( v ) , sz[u] += sz[v];
	if( u != s ) as = max( as , sz[u] );
}

void solve() {
	cin >> n >> m >> s;
	rep( i , 1 , m ) {
		int u , v , w;
		scanf("%d%d%d",&u,&v,&w);
		G[u].eb( mp( v , w ) ) , G[v].eb( mp( u , w ) );
	}
	dijk( );
	rep( u , 1 , n ) for( auto t : G[u] ) if( dis[t.fi] == dis[u] + t.se )
		g[u].pb( t.fi ) , rg[t.fi].pb( u ) , ++ deg[t.fi];
	queue<int> Q;
	Q.push( s );
	while( !Q.empty() ) {
		int u = Q.front(); Q.pop();
		for( int v : g[u] ) {
			-- deg[v];
			if( !deg[v] ) Q.push( v );
		}
		int cv = 0;
		for( int v : rg[u] ) {
			if( !cv ) cv = v;
			else cv = lca( cv , v );
		}
		dep[u] = dep[cv] + 1;
		if( !cv ) continue;
		J[u][0] = cv;
		Gt[cv].pb( u );
		rep( k , 1 , 17 ) if( J[J[u][k - 1]][k - 1] )
			J[u][k] = J[J[u][k - 1]][k - 1]; else break;
	}
	dfs( s );
	cout << as << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}