题面 P4606 [SDOI2018]战略游戏 Solution 圆方树上圆方果， 圆方树下你和我。 圆方树前建虚树， 欢乐多又多。 . 好吧，我们来说正题。 这题就比较强。根据常识，如果我们爆掉的点能影响这个图的连通性，那么，这个点一定是割点。 因此，我们要先对原图做Tarjan求点双。接下来，我们考虑用圆方树来解决一个问题。 我们先考虑暴力怎么做，我们先对原图求出圆方树。接下来，我们发现，对答案有贡献的点一定是孩子有被选定的点的圆点，并且这个点的总共被选定的孩子数不等于总共被选定数（因为如果这个点被割掉了，其被…

题面 传送门：洛谷 Solution 先跟我大声念： $\huge poi!$ . 然后开始干正事。 首先，我们先把题目中的点分为两类：去除这个点能把图分为几个部分的，去除这个点不影响整个图的连通性的。 如下图： 点上的数字表示这个点的搜索序。 我们称这些对连通性有影响的点为割点。 先假设我们能求出这些点以及其出去后把图分为几块之后那几块分别的大小。 是不是发现了什么？ 对于非割点，答案显然是$2*(n-1)$ (因为它不能影响别的点对连通性，能影响的只是别人到它以及它到别人) 对于割点，它把那几块弄得无法联通，即…

题面 传送门：洛谷 Solution 这题显然要先把缩点做了。 然后我们就可以考虑如何处理走反向边的问题。 像我这样的蒟蒻，当然是使用搜索，带记忆化的那种（滑稽）。 考虑设$f(i,j)$表示到达第i个点，还能走j次反向边，所能到达的最多的点的数量。 转移可以表示为： 如果x能到达1所在的强连通分量或max出来的值不为0，说明当前状态可行，否则不可行。 然后用记忆化搜索表达出来就OK了 Code #include<iostream> #include<cstdio> #include<…

题面 传送门：洛谷 Solution 前排提示，本蒟蒻做法既奇葩又麻烦 我们先可以把题目转换一下。 可以把一头牛喜欢另外一头牛理解为另外一头牛被一头牛喜欢。 我们把被喜欢的关系建边，即B被A喜欢，从B向A连一条有向边。 显然，一个点若能到达其他所有节点，它就是题目中的明星牛。 接下来，我们可以考虑一个类似于DP的做法。 即一个点能访问到的点，等同于它的儿子们访问的到的点加上它自己。 显然，这种特性要在DAG（有向无环图）上才能方便的使用。 所以说，我们第一步要对题目做的是缩点。 缩完点之后，我们就可以进行图上DP了…