[CodeChef]Curing Kingdom

[CodeChef]Curing Kingdom

题目

传送门 to CodeChef

思路

树的情况很简单，只能有一个叶子节点不是最初就染黑的。

图呢？发现我们要处理的问题是，删掉一个点（染黑）之后，图（白点）是否连通。所以我们会联想到 点双连通分量（感觉逻辑性很差啊）。

举几个例子会发现，对于一个点双，无论是最初染黑哪个点、最后染黑哪个点，总存在方案。所以我们 大胆猜测，点双缩点后，只能有一个叶子节点不是最初就染黑的；一个点双只需要染黑一个点，就等价于整个点双被染黑。联系到数据范围，这很有道理。

怎么构造方案呢？首先，我们要简化问题，可以假设每个点只有最多一条返祖边。因为这样不影响其点双连通性，而根据我们的猜测，这样也是可解的。

我试着去构造了一下，发现非常麻烦。不是不可做，只是很头疼。显然我们只需要考虑一个点双的情况。大体思路是，维护一条已有路径，它可以遍历 r o o t root root 到 x x x 的树上路径的点；由于是点双， x x x 子树内肯定存在某个点往 r o o t → x rootto x root→x 连边，那么我们就把它接上去就可以了。

听上去很简单，但是分叉点（多个儿子）呢？又怎么找这条非树边，然后更改路径呢？我确实觉得头大。

题解做法是怎样想到的？即使我想到不自顶向下，而是 自底向上，假如从叶子开始找，那就只需要保留叶子最浅的返祖边。可是这条边究竟是往上还是往下的呢？即使我想到，这只取决于旁边两个点谁先被染黑，我也无计可施啊！

所以题解是：对于一个叶子，它是 二度点，那么相邻的点有一个被染黑后，它就应该立刻被染黑。而这样一来，另一个邻居也成为了可以被染黑的状态。所以这实际上与两个邻居直接相连是等价的。

考虑将一个叶子删去，并将其相邻的两个点（父节点和返祖边指向的点）相连。新图仍然是点双，所以存在合法方案。在这两个点任意一个首次被染黑之后，立刻染黑该叶子，则得到原图的合法方案。

该过程的实现，则只需要再建一个 “递归状态图”：最初为空，删除叶子时，叶子的两个邻居往这个叶子连边。最后输出方案的时候，只需要 dfs text{dfs} dfs 就能让一个点被染黑的时候，连续涅很多点。

一个点有多个出边呢？则需要按照加边顺序访问。即，最先加入的边是最紧急的。这是显然的，因为除去第一条边，其余的边都是用来构造 “删去了第一个叶子” 之后的方案，而这个方案中出现第一个叶子的邻居时，必须立刻加入该叶子（而不是走其他边来继续构造新图的方案）。

不同点的出边之间，则无顺序的影响；因为 a → c ato c a→c 被使用，顶多带来的效果是 a , b a,b a,b 相连（二者原本中间有 c c c 点），也就影响 a → b ato b a→b 或 b → a bto a b→a 的边，不会影响到远方 i → j ito j i→j 的。

用上面的方法，我们可以将没被染黑的叶子都消除，最后只会剩下初始黑色点、最终黑色点（它是特殊点，不能删除）的一条链。而一条链的染黑方案很简单，就顺着链往上爬呗。调用 “递归状态图” 的 dfs text{dfs} dfs 就做完了。

对于多个点双的情况，当然可以每个点双建 dfs text{dfs} dfs 树；但事实上只需要一棵全局 dfs text{dfs} dfs 树。反正只要是 dfs text{dfs} dfs 树，都可以用这招；何必分别 dfs text{dfs} dfs 呢！

“顺着链往上爬” 的过程又是什么呢？把叶子点双没有初始黑色点的那个，提起来做根；那么顺着链往上爬，就是儿子节点被染黑后，直接把父节点也进行染黑操作呗。相当于在白色叶子都被消除后，得到的全是黑色叶子的树；自底向上全部涅光！

最后一个问题是，如果返祖边指向的点就是黑色点呢？显然这个点可以立刻被染黑。但是，这会影响它的父节点的判断（误以为自己是 “顺着链往上爬” 的部分）；所以我的代码中，决定先把这条边存下来，最后进行操作。当然你也可以用别的方法避免。

时间复杂度 O ( n + m ) mathcal O(n+m) O(n+m) 。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){int a = 0, c = getchar(), f = 1;for(; !isdigit(c); c=getchar())if(c == '-') f = -f;for(; isdigit(c); c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}const int MAXN = 500005;
struct Edge{int to, nxt, val;Edge() = default;Edge(int _t,int _n):to(_t),nxt(_n){}
};
Edge e[MAXN<<2];
int head[MAXN], cntEdge;
void addEdge(int a,int b){e[cntEdge] = Edge(b,head[a]);head[a] = cntEdge ++;
}const int INF = 0x3fffffff;
int dfn[MAXN], low[MAXN], dfsClock;
int tot, best[MAXN], w[MAXN], cnt_cut[MAXN];
bool cut[MAXN]; int sta[MAXN], top, tmp[MAXN];
void tarjan(int x,int pre){dfn[x] = low[x] = ++ dfsClock;sta[++ top] = x; int cntson = 0;for(int i=head[x]; ~i; i=e[i].nxt)if(dfn[e[i].to] == 0){tarjan(e[i].to,x);low[x] = min(low[x],low[e[i].to]);if(low[e[i].to] < dfn[x]) continue;cut[x] = true; ++ tot;if(!(~pre)) tmp[++ cntson] = tot;cnt_cut[tot] = best[tot] = 0;for(; sta[top+1]!=e[i].to; --top)if(cut[sta[top]]) ++ cnt_cut[tot];else if(w[sta[top]] < w[best[tot]])best[tot] = sta[top];// cannot do this in the middleif(cnt_cut[tot] && (~pre)) best[tot] = -1;}else if(e[i].to != pre)low[x] = min(low[x],dfn[e[i].to]);if(pre == -1){if(cntson == 1){if(w[best[tmp[1]]] > w[x])best[tmp[1]] = x; // as part of itif(cnt_cut[tmp[1]] > 1) best[tmp[1]] = -1;return void(cut[x] = false);}rep(i,1,cntson) if(cnt_cut[tmp[i]])best[tmp[i]] = -1; // invalid}
}bool fire[MAXN];
namespace Graph{vector<int> G[MAXN];void clear(int n){rep(i,1,n) G[i].clear();}void Amaterasu(int x){if(!fire[x]) printf("%d ",x);fire[x] = true; // always do sofor(const int &y : G[x])if(!fire[y]) Amaterasu(y);}void addEdge(int a,int b){G[a].push_back(b); // directed}
}
int build(int x,int pre){dfn[x] = ++ dfsClock, tmp[x] = 0;bool ignite = false;for(int i=head[x],y; ~i; i=e[i].nxt)if(dfn[y = e[i].to] == 0){const int v = build(y,x);if(fire[y]) ignite = true;if(!v) continue; // no edgeif(!tmp[x] || dfn[v] < dfn[tmp[x]])tmp[x] = v; // maybe lower than x}else if(y != pre && dfn[y] < dfn[x])if(!tmp[x] || dfn[y] < dfn[tmp[x]])tmp[x] = y; // index of nodeif(ignite || fire[x]) // or initial on firereturn Graph::Amaterasu(x), 0;if(~pre) Graph::addEdge(pre,x);if(!tmp[x] || dfn[tmp[x]] >= dfn[x])return 0; // no valid edge (cut)Graph::addEdge(tmp[x],x); return tmp[x];
}int main(){freopen("construct.in","r",stdin);freopen("construct.out","w",stdout);int n = readint(), m = readint();w[0] = INF; rep(i,1,n) w[i] = readint();memset(head+1,-1,n<<2);for(int a,b; m; --m){a = readint(), b = readint();addEdge(a,b), addEdge(b,a);}tarjan(1,-1); // connected graphint mx = top = 0; w[0] = -INF;rep(i,1,tot){if(!(~best[i])) continue;if(w[best[i]] > w[mx]){if(mx) sta[++ top] = mx;mx = best[i]; // hold}else sta[++ top] = best[i];}if(!top) sta[++ top] = mx;printf("%dn",top);rep(i,1,top){printf("%d ",sta[i]);fire[sta[i]] = true;}Graph::clear(n), dfsClock = 0;memset(dfn+1,0,n<<2); // reusebuild(mx,-1); // unchosen onereturn 0;
}

后记

最初我直接将题目转化为：找一个生成树，使得叶子的权值和最小。所以我的一个点双中，可能需要多个初始黑色点。我就这么想了 2 h 2h 2h，啥也没想出来。最后，我想了一个 “糖葫芦” 形的图，发现只需要染黑一个点？这才意识到，问题转化就根本是错的。

果然 O n e I n D a r k sf OneInDark OneInDark 对结果的基本反思能力都没有。真的超逊诶。尤其是在不擅长的图论题上。

我讨厌图论，因为它的 corner case text{corner case} corner case 太多了！在找到反例之前，我永远想象不出自己是怎么错的！小数据不够强，大数据又极难调试！火卓！

鸣谢

感谢这篇博客让我稍微对解决思路有了个方向。

感谢 O U Y E sf OUYE OUYE 能够不离不弃，努力解答愚蠢的 O n e I n D a r k sf OneInDark OneInDark 的问题，一次次地构造数据把我天真的想法 hack text{hack} hack 掉，并且最终帮我 debug text{debug} debug 出代码的问题。 O U Y E orz orz orz {sf OUYE}text{ orz orz orz} OUYE orz orz orz！

这一道题花费了我一天（虽然上午是白费了）和一个上午，才最终 A C AC AC，即使是在有 O U Y E sf OUYE OUYE 这样无私而强有力的帮助之下。果然我还是太弱了。就像鸣人面对着我爱罗的尸体时，那种无力回天的感觉。好在 O U Y E sf OUYE OUYE 就像千代婆婆。