题目链接 题意：一棵树，给出n-1个边权，然后q组查询，每组查询询问两个点之间的距离。 思路： dfs跑出根到每个点的距离，设为dis[i] 那么u,v两点的距离就是ans = dis[u]+dis[v]-2*dis[lca(u,v)]; 其中lca(u,v)为u,v的最近公共祖先。 这个式子是利用容斥，其实也很直观。。不理解的话画个图就好。 所以终点就是求两个点的LCA. 据说有好多种做法。今天学习了大概是最简单的一种？ 学习链接 //parent为并查集，FIND为并查集的查找操作 //QUERY为询问结点对集合 //TREE为基图有根树 Tarjan(u) visit[u] = true for each (u, v) in …

题意是说，给定一个有向图，对于每一条边，问是否是s到t的最短路上一定会经过的边． 如果是就输出yes 如果不是，问能否通过减少这条边的权值（减少的权值就是修理费用），使得这条边成为新的最短路上的边． 对于一条边是否一定是最短路上的边，我们可以从s做一遍最短路，然后反响建边，从t再做一遍最短路． 得到两个d1,d2数组 如果一条边d1[u] + d2[v] + w(u, v) = 最短路，那这条边在最短路上的边．但是未必不能缺少． 我们还要判断这条边是否是不能缺少的． 不能缺少的意思是说，如果没有这条边，就不能构成最短路． 那么这条边一定是桥． 我们可以用tarjan算法求桥． 据说是水题，不过图论还没怎么刷，所以对我来说还是很有难度 …