【IDEA】选票统计

发表于 2025-08-20 分类于 ACM ， idea 阅读次数：作者 Pomelorin

原创题目。

选票统计

G 国共 \(n\) 个城市，\(m\) 个双向道路把它们连接起来，每个城市都可以通过某条路径到达其他任何一个城市。

G 国为了减少建设开支，希望将 \(n-1\) 条道路建设为主干道使用，使得每个城市都可以通过这 \(n-1\) 条道路到达其他任何一个城市。G 国已经给出了一个建设方案。

居民们有拜访其他城市居民的需求，自然需要尽量少走路。如果对于一个城市，到达其他任何一个城市的最短距离和只走主干道到达此城市的最短距离均相等，那么这个城市内的居民就会同意这个建设方案。否则，他们就不会同意这个方案。

你作为 G 国的大臣，你提议通过民主投票来决定这个方案是否通过。于是，你需要找出哪些城市里的居民同意方案，哪些不同意方案。

形式化题意：

给出一张共 \(n\) 个点，\(m\) 条边的无向带权连通图 \(G\)，边权均为正整数。给定此图的一个生成树 \(T(G)\)，它包含原图中所有的点。

定义 \(D(i,j)\) 为 \(G\) 中结点 \(i\) 与结点 \(j\) 间的最短距离，\(F(i,j)\) 为 \(T(G)\) 中结点 \(i\) 与结点 \(j\) 间的最短距离。特殊地，\(D(i,i)=F(i,i)=0\)。

设变量 \(Q_i\) 的取值为：当且仅当满足 \(\forall j\in [1,n],D(i,j)=F(i,j)\) 时，\(Q_i\) 为 \(1\)；否则 \(Q_i\) 为 \(0\)。

求 \(Q_{1\sim n}\) 的值。

输入的第一行为两个正整数 \(n,m\)。

接下来 \(m\) 行，每行三个正整数 \(u_i,v_i,l_i\)，表示一条边权为 \(l_i\) 的无向边 \((u_i,v_i)\)。其中，给出的前 \(n-1\) 条边为给定生成树上的边。

输出一行 \(n\) 个数，第 \(i\) 个数为 \(Q_i\) 的值。

\(1<n<m\le10^{5},1\le u_i,v_i\le n,1\le l_i\le 10^9\)，所有数均为正整数。