P11287 [COTS 2017] 影响 Utjecaj 题解

这题怎么写啊，我复杂度还标错了，还有 Day2 T2 好难。

题目大意

给定 n 个点 m 条边的无向图，每个点有点权 a_i，有些点为关键点（x_i = 1）。保证无自环，但可能有重边。

你需要支持 q 次操作：

1. 修改某个点的点权。
2. 查询所有不经过别的关键点就能到关键点 u 的点的点权和。

其中 n, m, q \leq 2 \times 10^5，a_i \leq 10^9。

思路

显然，不能到达关键点 u 的点一定经过了其他关键点，或根本不与 u 连通，因此我们可以考虑直接把关键点删了，把剩下的连通块缩成一个点，再把关键点加回去。

此时每个关键点连到的连通块里的所有点都可以到达该关键点，查询的时候只需要关心关键点周围的若干个连通块即可。

我们先考虑两种不同的暴力：

1. 更改点权时直接暴力更新与它相邻的关键点的答案，此时修改 O(n)，查询 O(1)。
2. 更改点权时直接修改一个连通块的点权和，每次查询时直接暴力枚举与他相邻的非关键点连通块，对答案求和，此时修改 O(1)，查询 O(n)。

两种做法都可以被菊花图卡掉，不过这样已经有 10\text{pts} 了。

不过我们可以发现，第一种做法在领域数较小的普通点适用，第二种做法在领域数较小的关键点适用，因此考虑对度数根号分治。

记缩点后的点数、边数分别为 n', m'，此时无向图的度数和为 2m'，所以度数超过 \sqrt{m'} 的点不超过 2\sqrt{m'} 个。

这样一来，修改时对于度数不超过 \sqrt{m'} 的连通块，我们直接修改它的领域点的答案；对于度数超过 \sqrt{m'} 的连通块，我们直接给它打一个标记（即只修改自己的权值）；而在查询的时候，除了关键点自己的答案，我们还需要加上与关键点联通但度数大于 \sqrt{m'} 的连通块的点权，这样便是最后的答案。

注意些细节问题和写法，时间复杂度 O(n + q\sqrt{m})。

参考代码

写的很丑，请见谅。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int ll

const int N = 500000 + 10;
const int inf = 998244353;
using namespace std;

int read () {
    int x = 0, k = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') k = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return (1ll * x * k);
}

int n, m, q; 
int nn, bm;
int op, u, v;
int tp[N], a[N], b[N];
int col[N], dep[N];
vector<int> G[N], g[N]; 
unordered_set<int> H[N];

void bfs (int o) {
    static queue<int> Q;
    while (!Q.empty()) Q.pop();
    if (tp[o]) return b[o] += a[o], col[o] = o, void();
    Q.push(o); while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        if (col[u]) continue; col[u] = o, b[o] += a[u];
        for (int v: G[u]) if (!col[v] && !tp[v]) Q.push(v);
    }
}

signed main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) tp[i] = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= m; ++i) u = read(), v = read(), G[u].push_back(v), G[v].push_back(u);
    for (int i = 1; i <= n; ++i) if (!col[i]) bfs(i);
    for (int i = 1; i <= n; ++i) for (int v: G[i]) if (col[i] != col[v] && tp[i] + tp[v] != 2) H[col[i]].insert(col[v]), H[col[v]].insert(col[i]);
    for (int i = 1; i <= n; ++i) nn += (dep[i] = H[i].size()); bm = sqrt(nn);
    for (int i = 1; i <= n; ++i) if (tp[i]) for (int v: H[i]) (dep[v] <= bm) ? (b[i] += b[v]) : (g[i].push_back(v), 0);

    q = read();
    for (int i = 1; i <= q; ++i) {
        op = read(), u = read(), v = (op == 1) ? read() : 0;
        if (op == 1) {
            if (dep[col[u]] <= bm) for (int o: H[col[u]]) if (tp[o]) b[o] += v - a[u];
            b[col[u]] += v - a[u], a[u] = v;
        } else {
            int ret = b[u]; for (int o: g[u]) ret += b[o]; 
            cout << ret << endl;
        }
    }
    return 0;
}