跃迁引擎启动

ZOJ4059 Kawa Exam

发表于 更新于 分类于 阅读次数：

题面

给一个无向图，每个顶点本身有一个颜色 $a_i$，现在要给所有顶点分别染色，满足一个联通块内的顶点染的颜色必须相同。

对于每条边，分别询问删除这条边后，最多有多少顶点染的颜色和其本来的颜色相同。

$$
1 \le n,m,a_i \le 10^5, \sum n, \sum m \le 10^6
$$

分析

在一个联通块内，如果这条边在一个环内，删除这条边后，原联通块仍然联通。只有对于桥边，删除后会变成两个联通块，才会对答案有影响。

因此，首先需要用边双联通分量缩点，形成一个森林。

对于，森林内的每棵树，我们需要计算删除每一条树边后，子树内和子树外出现次数最多的次数，加上森林内其他树的答案即可。

对于子树内的众数，这是树上启发式合并，同样对于子树外的众数，反过来维护即可。

修改和查询最大值时，复杂度需要 $O(1)$。这里因为修改都是 $+1$ 或 $-1$，因此维护每种出现次数的个数即可。

注意：树上启发式合并时，缩点大小最好设置为对应块的大小。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <assert.h>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 998244353;
const int maxn = 200000 + 5;

inline int gi() {
    int r = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') r = r * 10 + ch - '0', ch = getchar();
    return r;
}

struct edge {
    int to, nxt, id;
} f[maxn * 2];
int head[maxn], eid;
inline void adde(int u, int v, int id) {
    f[++eid] = {v, head[u], id}; head[u] = eid;
}

vector<int> block[maxn];
int n, m, a[maxn], ans[maxn];

int tot, dfn[maxn], low[maxn], cnt, bel[maxn];
namespace Tarjan {
    edge f[maxn * 2];
    int head[maxn], eid, vis[maxn];
    inline void adde(int u, int v, int id) {
        f[++eid] = {v, head[u], id}; head[u] = eid;
    }
    int st[maxn], top;
    void dfs(int u, int eid) {
        // assert(u >= 1 && u <= n);
        // printf("%d\n", u);
        dfn[u] = low[u] = ++tot;
        st[++top] = u; vis[u] = 1;
        for (int i = head[u]; i; i = f[i].nxt) {
            int v = f[i].to, id = f[i].id;
            if (id == eid) continue;
            if (!dfn[v]) {
                dfs(v, id);
                low[u] = min(low[u], low[v]);
            } else if (vis[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            cnt++; int t = 0;
            do {
                t = st[top--];
                bel[t] = cnt;
                vis[t] = 0;
            } while (t != u);
        }
    }
    void init() {
        cnt = tot  = top = 0;
        for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i, 0);
        for (int i = 1; i <= n; i++) {
            block[bel[i]].push_back(i);
            for (int j = head[i]; j; j = f[j].nxt) {        
                int v = f[j].to;
                if (bel[i] != bel[v]) {
                    ::adde(bel[i], bel[v], f[j].id);
                } else ans[f[j].id] = 0;
            }
        }
    }
}

namespace DSU {
    int siz[maxn], son[maxn], ans2[maxn];
    bool vis[maxn], sk[maxn];
    int cnti[maxn], bagi[maxn], mxi, cnto[maxn], bago[maxn], mxo, allc; 
    inline void update(int x, int k) {
        bagi[cnti[x]]--; cnti[x] += k; bagi[cnti[x]]++;
        if (cnti[x] > mxi) mxi = cnti[x];
        if (bagi[mxi] == 0) mxi--;

        bago[cnto[x]]--; cnto[x] -= k; bago[cnto[x]]++;
        if (cnto[x] > mxo) mxo = cnto[x];
        if (bago[mxo] == 0) mxo--;
    }
    void add(int u, int f, int x) {
        for (auto it = block[u].begin(); it != block[u].end(); it++) {
            update(a[*it], x);
        }
        for (int i = head[u]; i; i = ::f[i].nxt) {
            int v = ::f[i].to;
            if (v == f || sk[v]) continue;
            add(v, u, x);
        }
    }
    void dfs(int u, int f, int kp) {
        vis[u] = 1; int sid = 0;
        for (int i = head[u]; i; i = ::f[i].nxt) {
            int v = ::f[i].to;
            if (v == son[u]) sid = ::f[i].id;
            if (v == f || v == son[u]) continue;
            dfs(v, u, 0);
            ans[::f[i].id] = ans2[v];
        }
        if (son[u]) dfs(son[u], u, 1), sk[son[u]] = 1;
        add(u, f, 1); 
        ans2[u] = mxo + mxi - allc;
        if (son[u]) sk[son[u]] = 0, ans[sid] = ans2[son[u]];
        if (!kp) add(u, f, -1);
    }
    void dfs1(int u, int f, int kp = 1) {
        for (auto it = block[u].begin(); it != block[u].end(); it++) {
            int x = a[*it];
            if (kp) {
                bago[cnto[x]]--; cnto[x]++; bago[cnto[x]]++;
                if (cnto[x] > mxo) mxo = cnto[x];
            } else {
                bago[cnto[x]]--; cnto[x]--; bago[cnto[x]]++;
            }
        }
        siz[u] = (int)block[u].size(); son[u] = 0; int m = -1;
        for (int i = head[u]; i; i = ::f[i].nxt) {
            int v = ::f[i].to;
            if (v == f) continue;
            dfs1(v, u, kp); siz[u] += siz[v];
            if (siz[v] > m) m = siz[v], son[u] = v;
        }
    }
    inline void solve() {
        int sum = 0;
        for (int i = 1; i <= cnt; i++) if (!vis[i]) {
            mxo = mxi = 0; bago[0] = bagi[0] = n;
            dfs1(i, 0); 
            allc = mxo; sum += allc;
            dfs(i, 0, 0);
            dfs1(i, 0, 0);
        }
        for (int i = 1; i <= m; i++) ans[i] += sum;
        for (int i = 1; i <= cnt; i++) vis[i] = 0, block[i].clear();
    }
}

int main() {
    int T = gi(); 
    while (T--) {
        eid = Tarjan::eid = 0;
        n = gi(); m = gi();
        for (int i = 1;  i <= n; i++) a[i] = gi();
        for (int i = 1, u, v; i <= m; i++) {
            u = gi(); v = gi();
            Tarjan::adde(u, v, i);
            Tarjan::adde(v, u, i);
        } 
        Tarjan::init();
        DSU::solve();
        for (int i = 1; i <= m; i++) printf("%d%c", ans[i], " \n"[i == m]);
        for (int i = 1; i <= n; i++) head[i] = Tarjan::head[i] = Tarjan::vis[i] = dfn[i] = 0;
    }
    return 0;
}