题解：P9886 [ICPC 2018 Qingdao R] Kawa Exam
PS：这题思维难度较低，代码难度较高。（或许是我的写法问题？）
容易想到如果删除的边在一个边双内，则答案和不删除这条边是一样的。 所以考虑先跑 tarjan 做一遍边双缩点，只有割边可能会改变答案。
然后将题目的模型转化，显然在同一个连通块内的点必须选择同一个选项。\ 所以一个连通块的贡献就是它内部出现次数最多的点权的次数。\ 然后显然，缩点之后会得到一个森林，存在于这个森林上的边就是原图中的割边。\ 可以想到对于森林中的每棵树，从根节点往下遍历，并在线维护子树内和子树外的最大出现次数。似乎可以线段树合并？但感觉很难写。
于是我放弃了线段树合并。显然，如果只需要统计子树，那么这题等价于 CF600E，太模板了就不讲了。\ 可是还要统计子树外？其实和子树内是同理，这里解释一下。
- 访问到一个节点，先记录答案。
- 然后加上这个点和它所有轻儿子的权值信息。
- 往下递归，先求出重儿子的答案。
- 然后再遍历每个轻儿子，先删除轻儿子的权值信息再往下递归轻儿子。
当 dfs 完一棵子树之后，统计数组内有存储这个子树的信息（因为步骤 2 中有加入这个点的点权）。\ 因此在求完重儿子答案之后不需要再把重儿子加入一遍。
代码真的很难写，可能我写的比较抽象吧 QwQ，但是确实一遍就过了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, M = 2e5 + 15;
int T, n, m, a[N];
int x[M], y[M];
int h[N], e[M], w[M], ne[M], idx = 0;
void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
int dfn[N], low[N], tot = 0;
bool cut[M];
void tarjan(int u, int pre) {
dfn[u] = low[u] = ++tot;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (!dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
if (dfn[u] < low[v]) cut[i] = cut[i ^ 1] = 1/*, cout << "Cut " << e[i] << ' ' << e[i ^ 1] << endl*/;
} else if (i != (pre ^ 1) ) {
low[u] = min(low[u], dfn[v]);
}
}
}
int ecc[N], cnt_ecc = 0;
void divide(int u) { //get ecc
ecc[u] = cnt_ecc;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (cut[i] || ecc[v]) continue;
divide(v);
}
}
void clr() {
for (int i = 0; i <= idx; i++) cut[i] = 0;
idx = tot = cnt_ecc = 0;
for (int i = 1; i <= n + 5; i++) h[i] = -1, dfn[i] = low[i] = ecc[i] = 0;
}
int cnt[N], ccnt[N], now; //now 是当前答案 ( Max )
void add(int x) { //加入一个数字
if (cnt[x]) ccnt[cnt[x]]--;
cnt[x]++, ccnt[cnt[x]]++;
if (now < cnt[x]) now = cnt[x];
}
void del(int x) { //删掉一个数字
ccnt[cnt[x]]--;
if (ccnt[cnt[x]] == 0 && now == cnt[x]) now--;
cnt[x]--;
if (cnt[x]) ccnt[cnt[x]]++;
}
struct Graph {
int h[N], e[M], w[M], ne[M], idx = 0;
int sz[N], dep[N], son[N];
vector<int> col[N]; //缩点后每个 点 的颜色列表
void Add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
void addedge(int a, int b, int c) { Add(a, b, c), Add(b, a, c); }
int ans_tree[N], ans_fa[N];
void init() {
memset(h, -1, sizeof h), idx = 0;
for (int i = 1; i <= cnt_ecc; i++) col[i].clear(), sz[i] = son[i] = dep[i] = ans_tree[i] = ans_fa[i] = 0;
}
void dfs1(int u, int father) {
sz[u] = 1, dep[u] = dep[father] + 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == father) continue;
dfs1(v, u), sz[u] += sz[v];
if (!son[u] || sz[son[u]] < sz[v]) son[u] = v;
}
}
void update(int u, int opt) { //对 u 点进行 opt 操作
// cout << "Update: " << u << ' ' << opt << endl;
if (opt == 1) for (int i : col[u]) add(i);
if (opt == -1) for (int i : col[u]) del(i);
}
void dfs(int u, int father, int opt) { //对 u 子树进行 opt 操作
update(u, opt);
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == father) continue;
dfs(v, u, opt);
}
}
void dfs_tree(int u, int father, bool keep) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == father || v == son[u]) continue;
dfs_tree(v, u, 0);
}
if (son[u]) dfs_tree(son[u], u, 1);
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == father || v == son[u]) continue;
dfs(v, u, 1);
}
update(u, 1);
ans_tree[u] = now;
if (!keep) dfs(u, father, -1);
}
void dfs_fa(int u, int father) {
ans_fa[u] = now, update(u, 1);
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == father || v == son[u]) continue;
dfs(v, u, 1);
}
if (son[u]) dfs_fa(son[u], u);
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == father || v == son[u]) continue;
dfs(v, u, -1);
dfs_fa(v, u);
}
}
void dfs_clr(int u, int father) {
for (int i : col[u]) ccnt[cnt[i]] = 0, cnt[i] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == father) continue;
dfs_clr(v, u);
}
}
} G;
int p[N];
int find(int x) { return (x == p[x]) ? x : p[x] = find(p[x]); }
void merge(int x, int y) {
x = find(x), y = find(y);
if (x ^ y) p[x] = y;
}
vector<int> c[N]; //缩点后每个 连通块 的颜色列表
int Ans[N], sum; //缩点后每个 连通块 不删的答案
bool st[N]; //连通块是否遍历过
void build_graph() {
for (int i = 1; i <= n; i++) c[i].clear();
G.init();
for (int i = 1; i <= n; i++) G.col[ecc[i]].push_back(a[i]);
for (int i = 1; i <= cnt_ecc; i++) st[i] = 0, p[i] = i;
for (int i = 1; i <= m; i++) {
int u = x[i], v = y[i];
if (ecc[u] == ecc[v]) continue;
G.addedge(ecc[u], ecc[v], i);
merge(ecc[u], ecc[v]);
}
for (int i = 1; i <= n; i++) c[ find(ecc[i]) ].push_back(a[i]);
sum = 0;
for (int i = 1; i <= cnt_ecc; i++) st[i] = 0;
for (int i = 1; i <= cnt_ecc; i++) {
int id = find(p[i]);
if (st[ id ]) continue; //每个连通块只处理一次 Ans
st[ id ] = 1;
int Max = 0;
for (int j : c[id]) cnt[j]++, Max = max(Max, cnt[j]);
Ans[ id ] = Max, sum += Max;
for (int j : c[id]) cnt[j]--;
}
for (int i = 1; i <= cnt_ecc; i++) st[i] = 0;
for (int i = 1; i <= cnt_ecc; i++)
if (!st[find(i)]) st[find(i)] = 1, G.dfs1(i, 0);
// for (int i = 1; i <= n; i++) cout << G.son[i] << ' '; puts("");
for (int i = 1; i <= cnt_ecc; i++) st[i] = 0;
for (int i = 1; i <= cnt_ecc; i++)
if (!st[find(i)]) {
st[find(i)] = 1, now = 0, G.dfs_tree(i, 0, 0);
G.dfs_clr(i, 0), now = 0;
// cout << "QwQ " << i << endl;
}
for (int i = 1; i <= cnt_ecc; i++) st[i] = 0;
for (int i = 1; i <= cnt_ecc; i++)
if (!st[find(i)]) {
st[find(i)] = 1, now = 0, G.dfs_fa(i, 0);
G.dfs_clr(i, 0), now = 0;
// cout << "AwA " << i << endl;
}
// G.dfs_tree(1, 0, 0);
// for (int i = 1; i <= 3; i++) cout << cnt[i] << ' '; puts("");
// for (int i = 1; i <= 3; i++) cout << ccnt[i] << ' '; puts("");
// exit(0);
}
void solve() {
scanf("%d%d", &n, &m);
clr();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d%d", &x[i], &y[i]), add(x[i], y[i], i), add(y[i], x[i], i);
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i, -1);
for (int i = 1; i <= n; i++)
if (!ecc[i]) ++cnt_ecc, divide(i);
build_graph();
// for (int i = 1; i <= n; i++) printf("%d\t%d %d\n", i, G.ans_tree[i], G.ans_fa[i]);
// for (int i = 1; i <= n; i++) cout << '\t' << i << ' ' << low[i] << endl;
for (int i = 1; i <= m; i++) {
int u = ecc[x[i]], v = ecc[y[i]];
if (u == v) printf("%d", sum);
else {
if (G.dep[u] < G.dep[v]) swap(u, v);
// cout << "Query: " << u << ' ' << v << ' ' << G.dep[u] << ' ' << G.dep[v] << endl;
printf("%d", sum - Ans[ find(u) ] + G.ans_tree[u] + G.ans_fa[u]);
}
putchar(i == m ? '\n' : ' ');
}
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}