感染 点分治优化建图

I 国有 \(n\) 个城市，有 \(n-1\) 条道路连接，并且所有的城市相互可达。城市因为自身的交通因素，人口因素，有一个传染力 \(r_i\) ，一旦这个城市爆发疫情，会迅速感染其他距离小于等于 \(r_i\) 的其他城市，并且造成连锁反应。

问一开始最少几个受到境外输入，会导致整个国家 \(n\) 个城市全部被感染。

为什么都写的这么复杂。首先就是建图 + Tarjan 强连通缩点后找入度为 \(0\) 个数。

重点就在这个优化建图。它十分地具有点分治的感觉。考虑点分治优化建图。

那么在固定算根为 \(u\) 的时候，直接 dfs 记录其子树中的点与其的距离 \(dis_v\)。那么 \(v_1\) 能向 \(v_2\) 连边即 \(dis_{v_1} + dis_{v_2} \leq r_{v_1}\)。转换成 \(dis_{v_2} \leq r_{v_1} - dis_{v_1}\)，那么把 \(dis\) 从小到大排序，枚举 \(v_1\)，满足的一定是一个前缀，用二分就能找到。那么就是一个前缀优化建图。新建虚点来表示前缀状态，然后长度差为 \(1\) 的前缀状态就长的连向短的，每一个前缀状态连向实际最末端的那个点。这样就可以枚举 \(v_1\) 然后连虚点了。然后用点分治优化整个过程。

最后一样的操作。注意跑 Tarjan 时只跑 \(1 \sim n\)，因为你显然不能直接从虚点开始，虚点只是起到一个辅助连边的作用。然后只看被访问到的就好了。

namespace liuzimingc {
#define endl '\n'
#define int long long
const int N = 1e7 + 5, INF = 1e18;

int n, r[N], dfn[N], dep[N], cnt, low[N], id[N], a[N];
int siz[N], mx[N], scc_cnt, scc_id[N], dis[N], in[N], sum, tot, rt;
bool vis[N];
vector<pair<int, int>> e[N];
vector<int> e2[N];
stack<int> s;
vector<pair<int, int>> now;

void get_root(int u, int fa) {
	siz[u] = 1;
	mx[u] = 0;
	for (const auto &i : e[u]) {
		int v = i.first;
		if (v == fa || vis[v]) continue;
		get_root(v, u);
		siz[u] += siz[v];
		mx[u] = max(mx[u], siz[v]);
	}
	mx[u] = max(mx[u], sum - siz[u]);
	if (mx[u] < mx[rt]) rt = u;
}

void dfs(int u, int fa) {
	now.push_back(make_pair(dis[u], u));
	for (const auto &i : e[u]) {
		int v = i.first, w = i.second;
		if (v == fa || vis[v]) continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
	}
}

void tree_divide(int u, int fa) {
	vis[u] = true;
	dis[u] = 0;
	now.clear();
	dfs(u, 0);
	sort(now.begin(), now.end());
	for (int i = 0; i < now.size(); i++) {
		a[i] = now[i].first;
		id[i] = ++tot;
		e2[id[i]].push_back(now[i].second);
		if (i) e2[id[i]].push_back(id[i - 1]);
	}
	for (int i = 0; i < now.size(); i++) {
		int d = r[now[i].second] - now[i].first;
		if (d < 0) continue;
		int x = upper_bound(a, a + now.size(), d) - a - 1;
		e2[now[i].second].push_back(id[x]);
	}
	for (const auto &i : e[u]) {
		int v = i.first;
		if (v == fa || vis[v]) continue;
		rt = 0;
		sum = siz[v];
		get_root(v, u);
		get_root(rt, 0);
		tree_divide(rt, 0);
	}
}

void tarjan(int u) {
	dfn[u] = low[u] = ++cnt;
	s.push(u);
	for (const int &v : e2[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (!scc_id[v]) low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		scc_cnt++;
		int t;
		do {
			t = s.top(); s.pop();
			scc_id[t] = scc_cnt;
		} while (t != u);
	}
} // 为了避免太多 dfs 决定使用 tarjan 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	mx[0] = INF;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> r[i];
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back(make_pair(v, w));
		e[v].push_back(make_pair(u, w));
	}
	sum = tot = n;
	rt = 0;
	get_root(1, 0);
	get_root(rt, 0);
	tree_divide(rt, 0);
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= tot; i++)
		for (const int &j : e2[i]) {
			if (!scc_id[i] || !scc_id[j]) continue;
			if (scc_id[i] != scc_id[j]) in[scc_id[j]]++;
		}
	int ans = 0;
	for (int i = 1; i <= scc_cnt; i++)
		if (!in[i]) ans++;
	cout << ans << endl;
	return 0;
}
#undef int
} // namespace liuzimingc