自动搬运

查看原文

来自洛谷，原作者为

	Conan15 天地正气，浩然长存，煌煌天威，以剑引之！

搬运于2025-08-24 22:52:43，当前版本为作者最后更新于2025-03-04 21:03:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

PS：这题思维难度较低，代码难度较高。（或许是我的写法问题？）

容易想到如果删除的边在一个边双内，则答案和不删除这条边是一样的。 所以考虑先跑 tarjan 做一遍边双缩点，只有割边可能会改变答案。

然后将题目的模型转化，显然在同一个连通块内的点必须选择同一个选项。
所以一个连通块的贡献就是它内部出现次数最多的点权的次数。
然后显然，缩点之后会得到一个森林，存在于这个森林上的边就是原图中的割边。
可以想到对于森林中的每棵树，从根节点往下遍历，并在线维护子树内和子树外的最大出现次数。似乎可以线段树合并？但感觉很难写。

于是我放弃了线段树合并。显然，如果只需要统计子树，那么这题等价于 CF600E，太模板了就不讲了。
可是还要统计子树外？其实和子树内是同理，这里解释一下。

1. 访问到一个节点，先记录答案。
2. 然后加上这个点和它所有轻儿子的权值信息。
3. 往下递归，先求出重儿子的答案。
4. 然后再遍历每个轻儿子，先删除轻儿子的权值信息再往下递归轻儿子。

当 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;
}