CodeChef – CUREK
简化题意
给你一张
n
n
n
个点
m
m
m
条边的无向连通图，保证不存在重边和自环。
这张图的每个点都是白色的，你想要把它们全都染成黑色。刚开始你可以选择一些点把它们染成黑色，并需要付出这些点权值之和的代价；接下来你每次可以选择一个和黑点相邻的白点，并把它染成黑色。你还需要保证在每一步操作（包括最开始染那些点）之后，所有白点的导出子图连通。
请你最小化你所需要付出的代价，并构造一组代价最小时的方案。
题解
黑点可能使得白点不连通，这提示我们往割点上面想。
如果某个初始黑点在割点上，那么除非初始黑点覆盖全图过半，否则一定会把白点分成不连通的几部分，这肯定是不优的。另外，对于只包含一个割点的点双连通分量，只有两种情况：
点双连通分量内初始存在至少一个黑点；
点双连通分量内初始无黑点，但在分量内出现第一个黑点前，图的其它部分已全黑。
所以，我们不妨合理猜测，最优方案一定是在所有这种“叶子点双”中，恰有一个内部初始无黑点，其它叶子点双内最开始都恰好存在一个不在割点上的黑点。
结论的必要性是显然的，而另一方面，我们也可(gan)以(shou)证(de)明(dao)只取这几个点一定可以合法地覆盖全图。
接下来的问题是，我们怎么构造出一种染色方案，使得我们的每一步染黑操作不会把白点的连通块烧断。
如果整个图是一棵树的话，那么我们的初始黑点一定在叶子或根上，而恰有一个度数为1的点不是黑点。我们只需要把这个点提出来当根，然后不断削叶子即可。
现在回到一般情况，在由点双连通分量构成的点双树上，恰有一个叶子点双里面初始没有黑点。我们把里面任意一个非割点提出来当根，建出一个DFS树过后，树上的叶子要么是黑的，要么一定存在至少一条返祖边。
既然是构造，那么我们不妨手动减少一些条件：删边，每个节点仅保留最浅的一条返祖边。此时相当于仅保留贡献了最小时间戳的边，不影响
t
a
r
j
a
n
\rm tarjan
t
a
r
j
a
n
算法，也就不影响点双联通性。如果删边后的图可以构造出合法方案，那么原图一定有一个一模一样的合法方案。
此时的叶子节点可以分两种情况讨论：
- 初始为黑点，那么可以在其父亲没有白点儿子的时候直接烧它，此时是从边缘烧，不影响白点连通性。
- 初始为白点，保留了一条返祖边，是二度点。对于一个二度点，我们总可以在其邻居染黑的时候立马把它也染黑，显然也不影响连通性。所以我们可以在它的邻居上打个标记，然后删除此节点并连接它的两个邻居，这样就变成了点数更少的子问题。
像这样，我们可以把所有白叶子都删去，然后像树的情况一样不断削黑叶子，在每个节点变黑的时候把标记释放，就可以构造出一个合法方案。（标记释放之后，新变黑的点虽然是已被删除的，上面也可能有标记，所以你要递归地释放并染色）
全程可以用一次DFS解决，只需要先模仿
t
a
r
j
a
n
\rm tarjan
t
a
r
j
a
n
算法求出最浅返祖边，然后判断儿子中是否有黑点。如果有，那么等遍历完所有儿子过后，把自己也染黑；否则，所有儿子一定已经全部删完，自己就成了一个叶子节点，如果自己本身不是黑点，那么就需要删去。
删掉的白叶子节点一定要记得把返祖边传给父亲。
每个将要染黑的点必须在遍历完所有儿子过后执行染色并释放标记。
标记的释放顺序很重要，一定是先打的先放，才可以还原出原图的一条链，所以可以用队列或
v
e
c
t
o
r
\rm vector
v
e
c
t
o
r
。
细节有点多，看代码吧。这已经是最简短的一份了。
代码
原题要求多组数据，但下面的代码没处理。
#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
#define END putchar('\n')
using namespace std;
const int MAXN=1000005;
const ll INF=1e18;
inline ll read(){
ll x=0;bool f=1;char s=getchar();
while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
return f?x:-x;
}
int ptf[30],lpt;
inline void print(ll x,char c='\n'){
if(x<0)putchar('-'),x=-x;
ptf[lpt=1]=x%10;
while(x>9)x/=10,ptf[++lpt]=x%10;
while(lpt)putchar(ptf[lpt--]^48);
if(c>0)putchar(c);
}
inline ll lowbit(ll x){return x&-x;}
struct edge{
int v,to;edge(){}
edge(int V,int T){v=V,to=T;}
}e[MAXN*3];
int EN=1,G[MAXN];
inline void addedge(int u,int v){
e[++EN]=edge(v,G[u]),G[u]=EN;
e[++EN]=edge(u,G[v]),G[v]=EN;
}
int n,m,k,dfn[MAXN],low[MAXN],bl[MAXN],IN;
ll w[MAXN];
int ps[MAXN<<1],tot;
vector<int>DS[MAXN<<1];
stack<int>st;
inline void tarjan(int x,int fa){
dfn[x]=low[x]=++IN,st.push(x);
for(int i=G[x];i;i=e[i].to){
if(i==fa)continue;
int v=e[i].v;
if(dfn[v])low[x]=min(low[x],dfn[v]);
else{
tarjan(v,i^1),low[x]=min(low[x],low[v]);
if(low[v]>=dfn[x]){tot++;
while(!st.empty()&&dfn[st.top()]>=dfn[v])
bl[st.top()]++,DS[tot].push_back(st.top()),st.pop();
DS[tot].push_back(x),bl[x]++;
}
}
}
}
bool blk[MAXN];
int dep[MAXN],lw[MAXN];
vector<int>nx[MAXN];
vector<int>as,bk;
inline void dfs_(int x){//递归放标记
for(auto&v:nx[x])
if(!blk[v])blk[v]=1,as.push_back(v),dfs_(v);
}
inline void dfs(int x,int fa){
dep[x]=dep[fa]+1,lw[x]=x;//深度或时间戳均可
bool ok=0;
for(int i=G[x];i;i=e[i].to){
int v=e[i].v;
if(v==fa)continue;
if(!dep[v]){
dfs(v,x);if(blk[v])ok=1;
if(dep[lw[v]]<dep[lw[x]])lw[x]=lw[v];
}
else if(dep[v]<dep[lw[x]])lw[x]=v;
}
if(ok&&!blk[x])as.push_back(x),blk[x]=1;
if(blk[x])dfs_(x);
else{
if(fa>0)nx[fa].push_back(x);
if(lw[x]^x)nx[lw[x]].push_back(x);
}
}
signed main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)w[i]=read();
for(int i=1;i<=m;i++)addedge(read(),read());
tarjan(1,0);
w[0]=0,w[n+1]=INF;
for(int i=1;i<=tot;i++){
for(auto&x:DS[i])if(bl[x]>1)ps[i]++;
if(ps[i]<2){
int u=n+1;
for(auto&x:DS[i])
if(bl[x]<2&&w[x]<w[u])u=x;
bk.push_back(u);
}
}
int rt=0;
if(bk.size()>1)for(auto&x:bk)if(w[x]>w[rt])rt=x;
for(auto&x:bk)if(x^rt)blk[x]=1,k++,as.push_back(x);
if(bk.size()<2)for(int i=1;i<=n;i++)if(!blk[i])rt=i,i=n;
dfs(rt,0);
print(k);
for(auto&x:as)print(x,' ');
END;
return 0;
}