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