题解/笔记 – [20231106NOIP模拟] 颜色限制（restriction）/ （树上）启发式合并

颜色限制（restriction）

时间限制: 1000ms
空间限制: 524288kB
输入文件名: restriction.in
输出文件名: restriction.out

题目描述

有一个 n 点 m 边的无向图，有 k 种颜色编号为 0∼k−1，每条边有一种颜色。对于每种颜色，请判断假如删去所有这种颜色的边，得到的图是否连通？是否是一棵树？

输入格式

从文件 restriction.in 中读入。
第一行三个整数 n,m,k ，表示点数、边数、颜色数。接下来 m 行，每行三个整数 u,v,c ，表示一条无向边(u,v) 的颜色为 c。

输出格式

输出到文件 restriction.out 中。
一行两个整数 p,q ，表示满足删去后图连通的颜色数和删去后图是树的颜色数。

样例

Input 1

5 5 4
1 2 0
2 3 0
3 4 1
4 5 2
5 2 3

Output 1

3 3

Input 2

5 5 2
1 2 0
2 3 0
3 4 0
4 5 0
5 2 0

Output 2

1 0

数据范围

对于全部数据：1\le n,m\le 10^5，2\le k\le 10^5，1\le u \neq v\le n，0\le c。
图无自环，但可能有重边。

样例解释

样例 1 解释

除了颜色 0 以外，其他颜色删去后均得到树，而删去0 图不连通。

题目分析

题面还是比较简单的，就是有各种颜色的边，问仅去掉一个边，图是否连通，是否为树。

先来看第二个小问。

问一个图 G\lang E, V \rang 是否为树，我们只要判断 \lbrack V = E – 1\rbrack 即可，做一个统计，复杂度 \mathcal{O}(m + k) 。

再看第一小问。

数据范围很大，每次遍历减去某个颜色的边绝对不行。我们先将颜色编号指向该颜色的边。
一开始想到，映射完毕之后可以将这些颜色加入到并查集，然后每次枚举去掉一个点之后的并查集，看是否连通。但是这样时间复杂度还是很高，为\mathcal{O}(k(m + n))。

所以我们就要介绍一种并查集的写法：

并查集启发式合并

启发式合并放弃了路径压缩，但是它尽可能地将这棵树压缩到最小。
很明显，我们根据树的大小或者深度合并，是最经济的做法。对于大部分可持久化算法，根据树的大小合并会节省一些空间。

具体做法：

开一个 cnt 数组，记录并查集的大小，初始化为1。在每次合并的时候，都将 cnt 小的一方合并到 cnt 大的一方。

并查集撤销

• 对于启发式并查集，如果我们知道合并顺序，其实可以开一个栈，正序合并，逆序拆解，具体可以看本题代码。
• 对于单点撤销，考虑别的做法。
  • 初始化的时候，维护一个数据范围之外的 cnt，在删除的时候，将删除的点的父亲挂载为 cnt ，并将 cnt 的父亲挂为 cnt 自己，cnt++。

扩展：树上启发式合并

做法讲解：

• 遍历每一个节点

• 递归解决所有的轻儿子，同时消除递归产生的影响

• 递归重儿子，不消除递归的影响

• 统计所有轻儿子对答案的影响

• 更新该节点的答案

• 删除所有轻儿子对答案的影响

例题（更新）

[例题] CF600E

我们继续看本题。思路其实跟树上问题类似，都是要利用重链部分对解进行计算。
考虑分治。设 solve(l,r) 表示解决删去的颜色在 [l,r] 时的问题。先将颜色在 [l,mid] 的边加到图中，递归 solve(mid+1,r) 即可求得删去的颜色在 [mid+1,r] 的所有答案；同理可以求得删去的颜色在 [l,mid] 的所有答案。使用可撤销并查集维护连通性即可。

AC Code

time: 806ms, memory: 9552kb, score: 100, status: Accepted
本题卡快读

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int MAXN = 1e5 + 100;
struct edge{int from, to;};
int fa[MAXN];
int cnt[MAXN];
int n, m, k;
vector<edge> G[100010];
inline void init() {
  for(int i = 1; i <= n; i++) {
    fa[i] = i, cnt[i] = 1;
  }
}
inline int read() {
  char ch = getchar(); int x = 0, f = 1;
  for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
  for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
int find(int pos) {
  return fa[pos] == pos ? pos : find(fa[pos]);
}
int ans1 = 0, ans2 = 0;
void dfs(int l, int r) {//访问到这里，应该是提前被删除或者没有加的
  if(l == r) {
    if(cnt[find(1)] == n) {
      ans1++;
      if(m - (int)G[l].size() == n - 1) ans2++;
    }
    return;
  }
  int mid = (l + r) >> 1;
  stack<pair<int, int>> st;
  for(int i = l; i <= mid; i++) {
    for(auto j : G[i]) {
      int u = find(j.from), v = find(j.to);
      if(u != v) {
        if(cnt[u] < cnt[v]) swap(u, v);
        st.emplace(u, v);
        fa[v] = u, cnt[u] += cnt[v];
      }
    }
  }
  dfs(mid + 1, r);
  while(!st.empty()) {
    auto t = st.top(); st.pop();
    fa[t.second] = t.second;
    cnt[t.first] -= cnt[t.second];
  }
  for(int i = mid + 1; i <= r; i++) {
    for(auto j : G[i]) {
      int u = find(j.from), v = find(j.to);
      if(u != v) {
        if(cnt[u] < cnt[v]) swap(u, v);
        st.emplace(u, v);
        fa[v] = u, cnt[u] += cnt[v];
      }
    }
  }
  dfs(l, mid);
  while(!st.empty()) {
    auto t = st.top(); st.pop();
    fa[t.second] = t.second;
    cnt[t.first] -= cnt[t.second];
  }
}
int main()
{
  freopen("restriction.in", "r", stdin);
  // freopen("restriction.out", "w", stdout);
 
  n = read(), m = read(), k = read();
  init();
  int u, v, c;
  for(int i = 1; i <= m; i++) {
    u = read(), v = read(), c = read();
    edge E;
    E.from = u, E.to = v;
    G[c].emplace_back(E);
  }
  dfs(0, k - 1);
  printf("%d %d\n", ans1, ans2);
  return 0;
}