P4350 easy Ad-hoc

简要题意

给你一个无向带权图，每次询问给定一个阈值，要求去掉权值小于阈值的边的子图中，按编号遍历每一个非孤立点，将 deg 恰好为 2 且不是自环的点的两边收缩为一条边，去掉该点，求非孤立点数量及边数。

思路

手玩一下。

考虑特殊情况,发现一条链会被收缩为 2点1边。
考虑较普遍的情况，考虑在主链上添加支链，发现收缩后链的交点会被保留。
考虑更普遍的情况，对于树，收缩后变成儿子数量不为 1 的节点构成的虚树。
这启发我们从点的 deg 考虑其是否会被收缩。

分析

step1

为保证复杂度，对于每一个询问我们一定不能按照编号一个一个操作，根据以上的手玩思路猜结论：

结论1：对于单个询问，点不被删去当且仅当该点 deg 不为 2，无论节点操作顺序如何。

证明：实际上，对于该结论，后者只是前者的充分不必要条件，我们暂且认为该结论是对的，其必要性的满足条件将在 step 3 进行讨论。其充分性的证明如下：

case1 收缩点的邻点不同，那么收缩不会改变其相邻点的 deg。
case2 收缩点的邻点相同，即该点与其唯一邻点存在重边，那么收缩会使邻点的 deg 减 1，并使邻点出现自环，那么即使邻点原先 deg 为 3 ，该邻点也会因为自环而不会被收缩。

这保证了无论如何改变节点编号，deg 不为 2 的点一定不会被删去。假如我们已经证明其必要性，那么我们可以通过计算 deg 为 2 的点来算出非孤立的点数。

step 2

显然我们不能对于每个询问都重构图，于是我们按询问的阈值排序，不断添加边，维护 deg 为 2 的点的个数 num。

非孤立点的个数显然，考虑如何通过 num 得到边答案。

结论2：剩余边数为不小于阈值的边数减去 num

证明：每删去一个点，则删去两边，添加一条边，结论显然。

我们似乎已经得到了无论思路还是代码都是绿题难度的解法？

step 3

手玩样例1发现 step 1 的结论1并不完全正确，对于 case2，当收缩前邻点的 deg 为 2 时，其可以因为自环免于被收缩，我们钦定其为 case3。因而结论1的必要性在 case3 的情景下是错误的。考虑什么时候出现 case3，由于题面保证无重边和自环，case2 的重边只有可能由三元环的一条边收缩而来。这启发我们一个结论。

结论3：对于询问，在每一次收缩前，每一个最多一点与外界链接的多元简单环对应着一个 case2, 每一个孤立多元简单环都对应着一个 case3。

证明：归纳地证明，手玩一下，一个孤立的简单

n

元环只有可能通过一个孤立简单

n+1

元环收缩而来。同样地一个孤立简单

n+1

元环都会收缩为

n

元环。最后他们会变成 case3 的二元环，被操作为一个一元环。

如果我们不考虑 case3，那么每一个孤立多元环被完全消灭，而实际它会变成一个一元环，错误地统计会使答案中的边数和点数少 1 。于是我们可以在维护 deg 为 2 点数 num 的同时，维护孤立简单多元环的个数 tag，最后在答案上均加上 tag 即可。

step 4

如何维护 tag？连通块为简单多元环当且仅当其所有点的 deg 均为2，我们只要在联通块 merge 时维护 size 和连通块中的 num 即可，若二者相等则 tag 增 1。

后记

事实上如果不考虑证明，这三个结论和其实现方式都是完全无法匹配其标签难度的，而结论的正确性也是一眼的。此题真正难度在于读懂不那么人话的翻译。

实现

CPP

#include<bits/stdc++.h>
using namespace std;
#define fst first
#define scd second
#define pii pair<int, int>
#define mkp make_pair
#define llg long long
const int N=5e5+5,mod=1e9+7,inf=1e9;

int deg[N],fa[N],siz[N],val[N];
int nod,del,edg,tag,n,m,q;
struct edge{
	int u,v,w;
}e[N];
bool cmp(edge a,edge b){
	return a.w<b.w;
}
pii p[N],ans[N];

int find(int x){
	return ((fa[x]==x) ? x : fa[x]=find(fa[x]));
}
void merge(int x,int y){
	if(x==y) return;
	fa[x]=y;
	siz[y]+=siz[x],val[y]+=val[x];
}
void solve(int u,int v){
	int x=find(u),y=find(v);
	nod+=(!deg[u])+(!deg[v]);
	del-=(deg[u]==2)+(deg[v]==2); 
	tag-=(siz[x]==val[x])+(x!=y)*(siz[y]==val[y]);
	val[x]-=(deg[u]==2); val[y]-=(deg[v]==2);
	
	edg++; merge(x,y);
	
	deg[u]++; deg[v]++;
	del+=(deg[u]==2)+(deg[v]==2);
	val[y]+=(deg[u]==2); val[y]+=(deg[v]==2);
	tag+=(siz[y]==val[y]);
}

int main(){
	cin>>n>>m;
	for(int i=1; i<=n; i++) siz[i]=1,fa[i]=i;
	for(int i=1; i<=m; i++){
		int u,v,w;
		cin>>u>>v>>w;
		e[i]={u,v,w};
	}	
	sort(e+1,e+m+1,cmp);
	cin>>q;
	for(int i=1; i<=q; i++){
		cin>>p[i].fst; p[i].scd=i;
	}
	sort(p+1,p+q+1);
	for(int i=q,j=m; i; i--){
		for(; j&&e[j].w>=p[i].fst; j--)
			solve(e[j].u,e[j].v);
		ans[p[i].scd]=mkp(nod-del+tag,edg-del+tag);
	}
	for(int i=1; i<=q; i++) cout<<ans[i].fst<<" "<<ans[i].scd<<"\n"; 
}

文章操作