Codechef MAY 15 Counting on a directed graph

题目大意
给定一张 n 个点 m 条边的有向图,一个点对 (X,Y) 是合法的当且仅当存在一条从 1 到 X 的路径,一条从 1到 Y 的路径满足
它们除了 1 号点以外没有任何公共点。
统计合法的无序对(X,Y) 的个数。

数据范围 n ≤ 105, m ≤ 5 × 105

吉如一的题解

可以发现一个点对 (X, Y ) 是合法的当且仅当从 1 出发,点 X 和点 Y 没有除了点 1 以外的公共必经点。
所以我们可以以 1 为根求出这张有向图的 dominator tree(支配树),那么点 X 和点 Y 是合法的条件就转化为了它们的 LCA 是点 1。
于是就可以对这一棵树DFS 一遍求出每一个子树的大小,然后扫一遍点1 的儿子得到答案。


要学习支配树相关知识点, 太晚了, 不写了

上一篇:纸张尺寸规格


下一篇:动画 | 什么是计数排序?