USACO2019.JAN Exercise Route

发表于 | 分类于 | ℃热度
~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

#.Exercise Route

简要翻译

奶牛Bessie意识到为了保持好的体形她需要更多地进行锻炼。她需要你帮助她选择在农场里每天用来晨跑的路线。 农场由N块草地组成，方便起见编号为$1…N$，由$M$条双向的小路连接。作为一种遵循规律的生物，奶牛们倾向于使用其中特定的$N−1​$条小路作为她们日常在草地之间移动的路线——她们管这些叫“常规的”小路。从每块草地出发都可以仅通过常规的小路到达所有其他草地。

为了使她的晨跑更加有趣，Bessie觉得她应该选择一条包含一些非常规的小路的路线。然而，使用常规的小路能够使她感到舒适，所以她不是很想在她的路线中使用过多非常规的小路。经过一些思考，她认为一条好的路线应当形成一个简单环（能够不经过任何草地超过一次的情况下回到起点），其中包含恰好两条非常规的小路。

请帮助Bessie计算她可以使用的好的路线的数量。两条路线被认为是相同的，如果它们包含的小路的集合相等。

Input

输入的第一行包含$N$和$M$。以下$M$行每行包含两个整数$a_i$和$b_i$，描述了一条小路的两端。其中前$N−1$条是常规的小路。

Output

输出一个整数代表Bessie可以选择的路线数。

Sample Input

5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2

Sample Output

4

Hint

$1≤N≤2×10^5$，$1≤M≤2×10^5$。

显然常规的小路就是一棵树（规定的树），非常规的小路就是非树边。

$Bessie$ 想要选择的路线，是一个简单环，即能够从起点出发回到起点的过程中至多经过其他所有的点一次，同时要求这个环上有两条非树边 。

我们可以自己手推出一个结论：

  • 每条非树边在树上两端点之间的路径如果和另一条非树边在树上两端点之间的路径有重边，那么树上的边加上这两条边就能组成一个环，而这两条非树边两端点树上路径之间的重边则不属于这个环。

（下文非树边在树上两端点之间的路径简称“graph”）

由这个结论又可以推得：

  • 如果两条graph1和graph2之间有重叠，则他们各自LCA1和LCA2下都可拆为两条链，判断这些链是否相交即可。重复计算的情况可从结果中记录减掉。

那怎么统计要减掉重复的路径呢？

我们回去看看题目，发现这题并没有在查询间的加入修改，那么可以离线处理。

在每一段询问区间的开始减掉最前端的节点在该区间之前的区间的数量；同时在每个区间的结尾加上最前端的节点在该区间的结尾之前的区间数量。

这样遍历一遍所有区间，然后再开始和结尾做差分处理，对于这个类似于做了差分处理的区间求前缀和，再遍历所有区间，每个区间进行答案的刚才做的统计的加减即可。

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
#include<cstdio>
#include<cctype>
#include<iostream>
#include<map>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
int n, m;
struct edge {
	int to, nxt;
} e[400010];
int linkk[400010], len;
void insert(int u, int v)
{
	e[++len].to = v, e[len].nxt = linkk[u], linkk[u] = len;
	e[++len].to = u, e[len].nxt = linkk[v], linkk[v] = len;
}
int fa[22][200010];
int depth[200010];
bool vis[200010];
pair<int, int> p[200010];
int bucket[200010], cnt[200010], ans[200010];
map<pair<int, int>, int> CntP;
void dfs(int x, int father)
{
	vis[x] = 1;
	depth[x] = depth[father] + 1;
	for (int j = 1; j <= 20; ++j)
		fa[j][x] = fa[j - 1][fa[j - 1][x]];
	for (int i = linkk[x]; i; i = e[i].nxt)
	{
		int to = e[i].to;
		if (to == father || vis[to]) continue;
		fa[0][to] = x;
		dfs(to, x);
	}
}
int lca(int x, int y)
{
	if (depth[x] < depth[y]) swap(x, y);
	for (int i = 20; ~i; --i)
		if (depth[fa[i][x]] >= depth[y])  x = fa[i][x];
	if (x == y) return x;
	for (int i = 20; ~i; --i)
		if (fa[i][x] != fa[i][y])
			x = fa[i][x], y = fa[i][y];
	return fa[0][x];
}
int gofront(int bottom, int top)
{
	if (bottom == top) return -521;
	for (int i = 20; ~i; --i)
		if (depth[fa[i][bottom]] > depth[top]) bottom = fa[i][bottom];
	return bottom;
}
void finddfs(int x, int t)
{
	cnt[x] = t;
	for (int i = linkk[x]; i; i = e[i].nxt)
	{
		int to = e[i].to;
		if (to == fa[0][x]) continue;
		finddfs(to, t + bucket[to]);
	}
}
long long res = 0;
int main(int argc, char const *argv[])
{
	n = read(), m = read();
	for (int i = 1; i < n; ++i)
	{
		int U = read(), V = read();
		insert(U, V);
	}
	dfs(1, 1);
	for (int i = 1; i <= m - n + 1; ++i)
	{
		p[i].first = read();
		p[i].second = read();
		ans[i] = lca(p[i].first, p[i].second);
		int x = gofront(p[i].first, ans[i]);
		if (x != -521)
			res -= bucket[x] + 1, ++bucket[x];
		int y = gofront(p[i].second, ans[i]);
		if (y != -521)
			res -= bucket[y] + 1, ++bucket[y];
		if (x != -521 && y != -521)
		{
			if (x > y) swap(x, y);
			res -= CntP[make_pair(x, y)];
			++CntP[make_pair(x, y)];
		}
	}
	finddfs(1, 0);
	for (int i = 1; i <= m - n + 1; ++i)
		res += cnt[p[i].first] + cnt[p[i].second] - (cnt[ans[i]] << 1);
	printf("%lld\n", res);
	return 0;
}
-------------本文结束(づ￣ 3￣)づ~感谢您的阅读(*╹▽╹*)-------------