专栏文章

题解：P9638 「yyOI R1」youyou 的军训

aakakal
P9638题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@minitpn8
此快照首次捕获于
2025/12/02 03:07
3 个月前
此快照最后确认于
2025/12/02 03:07
3 个月前
查看原文

solve\texttt{solve}

考虑是否适用于 kruskal 重构树，不难发现修改的限制条件“不改变相对顺序”就是防止重构树的形状发生改变设计的，只用单纯修改重构树上点权即可。
简单来说，这题就是瓶颈路问题的板子。
首先考虑跑一遍最大生成树。因为对于一个连接两个联通块的边 x↔yx\leftrightarrow y，若其权值 zz 小于另一条同样连接这个联通块的 x′↔y′x'\leftrightarrow y' 的权值 z′z'，当 x′↔y′x'\leftrightarrow y' 因为小于敏感度断掉时，x↔yx\leftrightarrow y 一定也断掉。因为没有边长这一说，所以这样选一定是不劣的。
进行操作一时，不妨先用一个变量 limitlimit 记录。初始设置为 −∞-\infty，这样不会有边断掉。
此时考虑在 limitlimit 的限制条件下进行操作 22。本质上就是寻找最大瓶颈，即找到 xx 的最浅祖先结点满足该结点的权值 ≥limit\ge limit。此时该子树内所有结点都在一个联通块里，叶子结点数量即为答案。
对于操作三，我们找到对应原边后修改这两个点的 lca\text{lca} 的权值即可。但是需要注意的是，因为这条边就算变大如果已经断掉了也不会恢复，那么我们需要把这个修改（如果有效）先存起来，进行新的操作一后更新。
排序建 kruskal 重构树是 O(mlog⁡m+m)O(m\log m+m)，修改找原边用映射 O(n)O(n)，求 lca\text{lca} 用树剖 O(log⁡n)O(\log n)，倍增找瓶颈 O(log⁡n)O(\log n)，跑 dfs 挂权值和树剖均是 O(n)O(n)。最劣的时间复杂度为 O(mlog⁡m+m+n+qlog⁡n)O(m\log m+m+n+q\log n)。

tips\texttt{tips}

  • 需要注意的是跑树剖不能只对 2n−12n-1 跑，因为不保证图强连通，最终可能是一个森林；
  • 倍增也需要对 2n−12n-1 跑。

code\texttt{code}

CPP
#include <bits/stdc++.h>
// #define int long long
#define lint long long
#define ldouble long double
#define endl '\n'
using namespace std;
const int N = 4e5+5;

struct edge{
	int idx,x,y,z;
	bitset<1> is;

	edge(int a = 0,int b = 0,int c = 0,int d = 0):
		idx(a),x(b),y(c),z(d) {}

	bool operator <(const edge &other) const {
		return this->z < other.z;
	}
	bool operator >(const edge &other) const {
		return this->z > other.z;
	}
}e[N];
int table[N];

struct node{
	int x,y,z;
}history[N];
int cnt;

int n,m,q;
int f[N<<1];
int limit;

vector<int > g[N<<1];
int cntId,id[N<<1];
int fa[N<<1][30],dep[N<<1];
int sz[N<<1],wson[N<<1];
int top[N<<1],val[N<<1];
int cntLeaves[N<<1];

inline int find(int x){
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}

inline void dfs1(int x,int father){
	fa[x][0] = father,sz[x] = 1;
	dep[x] = dep[father] + 1;
	for(int y : g[x]){
		if(y == father)
			continue;
		dfs1(y,x);
		sz[x] += sz[y];
		if(sz[y] > sz[wson[x]])
			wson[x] = y;
	}
}

inline void dfs2(int x,int TOP){
	id[x] = ++cntId;
	top[x] = TOP;
	if(wson[x]){
		dfs2(wson[x],TOP);
		cntLeaves[x] += cntLeaves[wson[x]];
	}else cntLeaves[x] = 1;
	for(int y : g[x]){
		if(y != fa[x][0] && y != wson[x]){
			dfs2(y,y);
			cntLeaves[x] += cntLeaves[y];
		}
	}
}

inline int lca(int x,int y){
	if(find(x) != find(y))
		return 0;

	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]])
			swap(x,y);
		x = fa[top[x]][0];
	}
	return dep[x] < dep[y] ? x : y;
}

inline int query(int x){
	int idx = 0;
	while(fa[x][idx] && val[fa[x][idx]] >= limit)
		idx++;
	
	if(idx == 0) return 1;

	idx--;
	while(idx >= 0){
		if(val[fa[x][idx]] >= limit)
			x = fa[x][idx];
		idx--;
	}

	return cntLeaves[x];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;

	int x,y,k;
	for(int i = 1; i <= m; i++){
		cin >> x >> y >> k;
		e[i] = edge(i,x,y,k);
		e[i].is.reset();
	}

	sort(e+1,e+1+m,greater<edge>());

	for(int i = 1; i <= (n<<1); i++)
		f[i] = i;

	for(int i = 1; i <= m; i++)
		table[e[i].idx] = i;

	int cntNode = n;
	for(int i = 1; i <= m; i++){
		int x = e[i].x,y = e[i].y;
		int fx = find(x),fy = find(y);
		if(fx != fy){
			e[i].is.set();
			val[++cntNode] = e[i].z;
			f[fx] = cntNode,f[fy] = cntNode;
			g[fx].push_back(cntNode),g[cntNode].push_back(fx);
			g[fy].push_back(cntNode),g[cntNode].push_back(fy);
		}
		if(cntNode == (n<<1)-1)
			break;
	}

	val[0] = -1;
	for(int idx = cntNode; idx >= 1; idx--){
		if(!id[idx]){
			dfs1(idx,0);
			dfs2(idx,idx);
		}
	}

	for(int j = 1; (1<<j) <= (n<<1); j++)
		for(int i = 1; i <= (n<<1); i++)
			fa[i][j] = fa[fa[i][j-1]][j-1];
	int op;
	while(q--){
		cin >> op;
		if(op == 1){
			cin >> x;
			limit = x;

			for(int i = 1; i <= cnt; i++)
				val[lca(history[i].x,history[i].y)] = history[i].z;
            cnt = 0;
		}else if(op == 2){
			cin >> x;
			cout << query(x) << endl;
		}else if(op == 3){
			cin >> x >> y;
			edge p = e[table[x]];
			if(p.is == true)
				history[++cnt] = (node){p.x,p.y,y};
		}
	}
	return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...