BZOJ3331《[BeiJing2013]压力》

十一月 03, 2019 5055

题意

给你一张 n 个点 m 条边的无向图，再给你 q 个点对，让你计算对于每一个点，有多少个点对间的路径必定经过这个点。N≤100000,M,Q≤200000。

解析

首先可以发现这样一个东西：

在原图对应的圆方树上，一个点对之间的所有圆点都会被经过

那就好做了

首先建出圆方树，然后问题转化为了一个树上链修改，单点查询的题目

直接树上差分一下就行了

我还是讲一下这个差分吧

具体就是对于点对(u,v)，diff[u]++, diff[v]++, diff[LCA(u,v)]--, diff[father[LCA(u,v)]]--

最后一遍 dfs 还原一下树上前缀和即可

代码实现

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
//
// Created by HandwerSTD on 2019/11/2.
// Copyright (c) 2019 HandwerSTD. All rights reserved.
// Title: [BeiJing2013]压力
//
// sto Qingyu orz
// 感谢真神sqy无私的教诲。膜时队者处处阿克，只因大师sqy在他背后。不膜大师者违背了真神的旨意，真神必将降下天谴，
// 使其天天爆零
// 我不由自主地膜拜真神sqy。
//

#include <cstdio>
#include <vector>

const int MAXN = 200000 + 10;
const int NEWN = MAXN << 1;
const int MAXQ = 200000 + 10;

struct Node {
    int next; bool typ;
    Node(int _next = 0, bool _typ = false) { next = _next; typ = _typ; }
};

struct qu { int u, v; qu(int _u = 0, int _v = 0) { u = _u; v = _v; } } qs[MAXQ];

int n, tn, m, q;

std::vector<int> head[MAXN];
std::vector<int> tree[NEWN];

namespace Tarjan {
    static int dfn[MAXN], low[MAXN], timestamp;
    static int stk[MAXN], top;

    void work(int, int);

    void tarjan() {
        tn = n;
        for (int i = 1; i <= tn; ++i) if (!dfn[i]) work(i, 0);
    }
    void work(int u, int fa) {
        dfn[u] = low[u] = ++timestamp;
        stk[++top] = u;
        for (int i = 0, siz = (int) head[u].size(); i < siz; ++i) {
            int v = head[u][i];
            if (!dfn[v]) {
                work(v, u);
                low[u] = std::min(low[u], low[v]);
                if (low[v] >= dfn[u]) {
                    int x = -1; ++tn; // 直接在这里建圆方树，++tn 是给圆方树的方点分配编号
                    do {
                        x = stk[top--];
                        tree[tn].push_back(x);
                        tree[x].push_back(tn);
//                        printf("Edge connected: <%d, %d>\n", tn, x);
                    } while (x != v);
                    tree[u].push_back(tn); tree[tn].push_back(u);
//                    printf("Edge connected: <%d, %d>\n", tn, u);
                }
            } else if (v != fa) low[u] = std::min(low[u], dfn[v]);
        }
    }
}

namespace LCA {
    static int father[NEWN][30], depth[NEWN];
    static int lg[NEWN];

    void dfs(int, int);

    void init() {
        for (int i = 1; i <= tn; ++i) {
            lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
        }
        dfs(1, 0);
    }
    void dfs(int u, int fa) {
        father[u][0] = fa; depth[u] = depth[fa] + 1;
        for (int i = 1; (1 << i) <= depth[u]; ++i) {
            father[u][i] = father[father[u][i - 1]][i - 1];
        }
        for (int i = 0, siz = (int) tree[u].size(); i < siz; ++i) {
            int v = tree[u][i];
            if (v != fa) dfs(v, u);
        }
    }
    int get(int u, int v) {
        if (depth[u] < depth[v]) std::swap(u, v);
        while (depth[u] > depth[v]) {
            u = father[u][lg[depth[u] - depth[v]] - 1];
        }
        if (u == v) return u;
        for (int i = lg[depth[u]]; i >= 0; --i) {
            if (father[u][i] != father[v][i]) {
                u = father[u][i]; v = father[v][i];
            }
        }
        return father[u][0];
    }
}

namespace Difference {
    static int diff[NEWN];

    void modify(int u, int v) {
        int l = LCA::get(u, v);
//        printf("u = %d, v = %d, LCA<%d, %d> = %d, LCA's father = %d\n", u, v, u, v, l, LCA::father[l][0]);
        ++diff[u]; ++diff[v];
        --diff[l]; --diff[LCA::father[l][0]];
    }
    void dfs(int u) {
//        printf("[dfs(u)] u = %d\n", u);
        using LCA::father;
        for (int i = 0, siz = (int) tree[u].size(); i < siz; ++i) {
            int v = tree[u][i]; if (v == father[u][0]) continue;
            dfs(v);
            diff[u] += diff[v];
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= m; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        head[u].push_back(v); head[v].push_back(u);
    }
    for (int i = 1; i <= q; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        qs[i] = qu(u, v);
    }
    Tarjan::tarjan();
    LCA::init();
    for (int i = 1; i <= q; ++i) {
        int u = qs[i].u, v = qs[i].v;
//        printf("Query #%d: u = %d, v = %d\n", i, u, v);
        Difference::modify(u, v);
    }
    Difference::dfs(1);
    for (int i = 1; i <= n; ++i) {
        printf("%d\n", Difference::diff[i]);
    }
    return 0;
}