ZJOI2019 语言

[ZJOI2019] 语言

$\text{ZJOI}\ 2019$ 半年过去了,发现当时的自己真的好菜,考场上只能打打暴力。

于是我决定补这道题的坑。

Description

九条可怜是一个喜欢规律的女孩子。按照规律,第二题应该是一道和数据结构有关的题。

在一个遥远的国度,有 $n$ 个城市。城市之间有 $n - 1$ 条双向道路,这些道路保证了任何两个城市之间都能直接或者间接地到达。

在上古时代,这 $n$ 个城市之间处于战争状态。在高度闭塞的环境中,每个城市都发展出了自己的语言。而在王国统一之后,语言不通给王国的发展带来了极大的阻碍。为了改善这种情况,国王下令设计了 $m$ 种通用语,并进行了 $m$ 次语言统一工作。在第 $i$ 次统一工作中,一名大臣从城市 $s_i$ 出发,沿着最短的路径走到了 $t_i$,教会了沿途所有城市(包括 $s_i, t_i$)使用第 $i$ 个通用语。

一旦有了共通的语言,那么城市之间就可以开展贸易活动了。两个城市 $u_i, v_i$ 之间可以开展贸易活动当且仅当存在一种通用语 $L$ 满足 $u_i$ 到 $v_i$ 最短路上的所有城市(包括 $u_i, v_i$),都会使用 $L$。

为了衡量语言统一工作的效果,国王想让你计算有多少对城市 $(u, v)$,他们之间可以开展贸易活动。

Solution

考虑求出每个点 $u$ 能够到达多少不同的点 $a[u]$ ,则答案为 $\displaystyle \frac{\sum a[u]} {2}$ 。

$c[x][y]$ 表示 $x$ 与 $y$ 是否可达。

先树剖,动态开点线段树维护上面那个东西,对一条路径 $(u, v)$ 上的所有点都进行区间修改,复杂度 $\mathcal{O} (n ^ 2 \log ^ 2 n)$ ,很优秀。

可是这样还是只能拿 $20$ 分,差一点(也就一个 n 的差距),如果能优化一下就好了。

仔细想一想,会发现这东西是一个类似树上差分的过程,若 $c[x][y]$ 的真正意义是 $x$ 被 $y$ 覆盖了几次,那么我们就相当于在 $u$ 与 $v$ 同时修改,回溯时在 $fa[lca_{u, v}]$ 处消除影响。线段树合并可以很好地帮助我们解决这个问题。

有一个比较巧妙的想法是看了题解之后才了解的,就是我们 $\text{pushup}$ 的时候只需要关注这个节点的标记是否是正的,这样可以省去 $\text{pushdown}$ 。

还有一个稍微值得注意的地方:对于某个点路径修改时,你势必会对其本身也进行修改,而始终没被走过的点则不会被自己修改,我们在统计答案时会出现问题,那么我们不如强制对于每个点修改其本身,最后减去即可(。

Code

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
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

inline int Split() {
int x = 0; char c = getchar();
while (c < 48 || c > 57) c = getchar();
while (c >= 48 && c <= 57) x = x * 10 + (c ^ 48), c = getchar();
return x;
}

const int N = 1e5;
int n, m, idx, dep[N + 5], siz[N + 5], son[N + 5], dfn[N + 5], top[N + 5], fa[N + 5];
long long ans;
std::vector<int> E[N + 5];
std::vector<std::pair<int, int>> Vec;
std::vector<std::pair<std::pair<int, int>, int>> Q[N + 5];

void Dfs1(int u, int f) {
dep[u] = dep[f] + 1;
siz[u] = 1, fa[u] = f;
for (const int &v : E[u]) {
if (v == f) continue;
Dfs1(v, u), siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}

void Dfs2(int u, int topf) {
top[u] = topf;
dfn[u] = ++idx;
Q[u].push_back(std::make_pair(std::make_pair(dfn[u], dfn[u]), 1));
if (fa[u] != 0) Q[fa[u]].push_back(std::make_pair(std::make_pair(dfn[u], dfn[u]), -1));
if (son[u]) Dfs2(son[u], topf);
for (const int &v : E[u])
if (v != fa[u] && v != son[u])
Dfs2(v, v);
}

struct Node {
int ls, rs, val, tag;
};

struct Segment_Tree {
int cnt, rt[N + 5];
Node tr[N << 8];
inline void Pushup(int p, int l, int r) {
if (tr[p].tag > 0) tr[p].val = r - l + 1;
else tr[p].val = tr[tr[p].ls].val + tr[tr[p].rs].val;
}
void Modify(int p, int l, int r, int x, int y, int v) {
if (l >= x && r <= y) return (void) (tr[p].tag += v, Pushup(p, l, r));
int mid = (l + r) >> 1;
if (x <= mid) {
if (tr[p].ls == 0) tr[p].ls = ++cnt;
Modify(tr[p].ls, l, mid, x, y, v);
}
if (y > mid) {
if (tr[p].rs == 0) tr[p].rs = ++cnt;
Modify(tr[p].rs, mid + 1, r, x, y, v);
}
Pushup(p, l, r);
}
int Merge(int p, int q, int l, int r) {
if (p == 0 || q == 0) return p | q;
tr[p].tag += tr[q].tag;
if (l == r) return Pushup(p, l, r), p;
int mid = (l + r) >> 1;
tr[p].ls = Merge(tr[p].ls, tr[q].ls, l, mid);
tr[p].rs = Merge(tr[p].rs, tr[q].rs, mid + 1, r);
return Pushup(p, l, r), p;
}
inline void Modify(int u, int l, int r, int v) {
Modify(rt[u], 1, n, l, r, v);
}
inline void Merge(int u, int v) {
rt[u] = Merge(rt[u], rt[v], 1, n);
}
} Tree;

inline int LCA(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
Vec.push_back(std::make_pair(dfn[top[u]], dfn[u]));
u = fa[top[u]];
}
if (dep[u] > dep[v]) std::swap(u, v);
Vec.push_back(std::make_pair(dfn[u], dfn[v]));
return u;
}

void Dfs(int u) {
for (const int &v : E[u]) {
if (v == fa[u]) continue;
Dfs(v);
Tree.Merge(u, v);
}
for (const std::pair<std::pair<int, int>, int> &p : Q[u])
Tree.Modify(u, p.first.first, p.first.second, p.second);
ans += Tree.tr[Tree.rt[u]].val;
}

int main() {
n = Split(), m = Split();
for (int i = 1; i < n; ++i) {
int u = Split(), v = Split();
E[u].push_back(v);
E[v].push_back(u);
}
Dfs1(1, 0), Dfs2(1, 1);
for (int i = 1; i <= m; ++i) {
int u = Split(), v = Split(), lca = LCA(u, v);
for (const std::pair<int, int> &p : Vec) {
Q[u].push_back(std::make_pair(p, 1));
Q[v].push_back(std::make_pair(p, 1));
if (fa[lca] != 0) Q[fa[lca]].push_back(std::make_pair(p, -2));
}
Vec.clear();
}
Tree.cnt = n;
for (int i = 1; i <= n; ++i)
Tree.rt[i] = i;
Dfs(1);
printf("%lld\n", (ans - n) >> 1);
return 0;
}