P5680 [GZOI2017] 共享单车

GZOI2017 D2T3

某校校内有 A 公司与 B 公司两家共享单车公司相互竞争。A 公司为了尽可能提升自己在校园内的占有率，会设法阻碍 B 公司的回收行动。 整个校园由 $N$ 个区域和 $M$ 条道路组成，每条道路连接两个区域。校园有一个区域 $K$ 是 B 公司的大本营，所有的单车回收行动从该区域 **出发**。B 公司为了减少成本，回收时从区域 $K$ 到任何一个区域 $X$ 都选择长度 **最短** 的路径，如果有多条到某一个区域的最短路径，则选择所有最短路径中该区域的前一区域 **编号最小** 的一条路径，称这条路径为 $K$ 到 $X$ 的 **回收路线**。所有的 **回收路线** 组成一棵树状结构，称之为 **回收路线树**。如下图中，绿色的边构成的就是一棵 **回收路线树**。  B 公司每次会回收若干个区域的单车，称这些区域为 **回收区域**。B 公司还将某些区域设为 **投放区域**，称其余区域为 **非投放区域**。在 **回收路线树** 上，标记出区域 $K$，标记出所有的 **回收区域**，以及标记出任意两个 **回收区域** 在 **回收路线树** 上的最近公共祖先。 如下图，假设 $4$ 与 $6$ 号区域是 **投放区域**，$4, 5, 6$ 号区域是**回收区域**，则被标记的区域有 $1, 4, 5, 6$。  A 公司对 B 公司的回收行动造成了阻碍，**当且仅当** 对任意一个 $K$ 以外的被标记的 **投放区域** $X$，从区域 $K$ 到 $X$ 的 **回收路线上** 都存在两个被标记的区域，它们之间 **所有道路**（回收路线树上两点路径）被阻碍。 阻碍一条道路的代价为该道路的长度。上图中 A 公司选择阻碍 $1 \rightsquigarrow 4$，$5 \rightsquigarrow 6$ 两条路径，代价为 $3+4+3=10$。 你的任务是帮助 A 公司计算如何以最小的代价，阻碍 B 公司的回收行动。

无

无

【数据约束】 对于 $30\%$ 的数据，$N\le 200$，$Q\le 200$； 对于 $60\%$ 的数据，保证每次 **回收区域** 数量恒为 $N-1$； 对于 $80\%$ 的数据，$N\le 20000$，$M=N-1$，$Q\le 1000$，$num\le 200$； 对于 $100\%$ 的数据，$N\le 50000$，$M\le 100000$，$Q\le 1500$，$num\le 500$。 所有数据保证道路无自环，所有道路长度小于 $2000$，且区域 $K$ 任意时刻均非**投放区域**。