前置：莫队，LCA（太简单了懒得写(bushi)） 1. 树 -> 链 用欧拉序将树转化成序列，然后我们可以发现： 若 \text{lca}(u,v) = u，u \to v 的路径为 in_u 到 in_v 的区间中所有只出现一次的点构成的路径。 若 \text{lca}(u, v) \ne u，
\mathtt{TAG}：最短路，DP，拓扑排序 题意 给定一个 n 个点 m 条边的无向图，边有边权。 给定两对点 s_1,t_1 和 s_2,t_2。 你可以选定 s_1 到 t_1 的一条最短路径，使得这些边的边权变为 0
发布于 2024-09-14
