「BZOJ-3772」精神污染-主席树

兵库县位于日本列岛的中央位置,北临日本海,南面濑户内海直通太平洋,中央部位是森林和山地,与拥有关西机场的大阪府比邻而居,是关西地区面积最大的县,是集经济和文化于一体的一大地区,是日本西部门户,海陆空交通设施发达。濑户内海沿岸气候温暖,多晴天,有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市,还有以疗养地而闻名的六甲山地等。
兵库县官方也大力发展旅游,为了方便,他们在县内的N个旅游景点上建立了n-1条观光道,构成了一棵图论中的树。同时他们推出了M条观光线路,每条线路由两个节点x和y指定,经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。
你和你的朋友打算前往兵库县旅游,但旅行社还没有告知你们最终选择的观光线路是哪一条(假设是线路A)。这时候你得到了一个消息:在兵库北有一群丧心病狂的香菜蜜,他们已经选定了一条观光线路(假设是线路B),对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路,比如有四个景点1-2-3-4,而【精神污染】的路径是1-4,那么1-3,2-4,1-2等路径也被视为被完全污染了。
现在你想知道的是,假设随便选择两条不同的路径A和B,存在一条路径使得如果这条路径被污染,另一条路径也被污染的概率。换句话说,一条路径被另一条路径包含的概率。

链接

bzoj

输入

第一行两个整数 $N,M$
接下来 $N-1$ 行,每行两个数 $a,b$,表示 $A$ 和 $B$ 之间有一条观光道。
接下来 $M$ 行,每行两个数 $x,y$,表示一条旅游线路。

输出

所求的概率,以最简分数形式输出。

样例数据

输入

1
2
3
4
5
6
7
8
5 3
1 2
2 3
3 4
2 5
3 5
2 5
1 4

输出

1
1/3

样例解释

可以选择的路径对有 $(1,2),(1,3),(2,3)$,只有路径 $1$ 完全覆盖路径 $2$。
100%的数据满足:$N,M<=100000$

题解

详见PoPoQQQ

我们维护入栈出栈序,将每个点维护一个可持久化线段树 版本是父亲版本加上该节点的vector中所有元素在入栈出栈序上的位置,由于是入栈出栈序,因此入栈为 $1$,出栈为 $-1$,由于入栈出栈序只能查询一个节点指向根的一条链,因此我们将 $[x,y]$ 这条链拆成 $[x,lca]$ 和 $[lca,y]$ 两段,这其中由于 $lca$ 被算了两次,因此还要减掉$[lca,lca]$ 就可以了。

代码

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
#include <bits/stdc++.h>
inline char read() {
static const int IO_LEN = 1024 * 1024;
static char buf[IO_LEN], *ioh, *iot;
if (iot == ioh) {
iot = (ioh = buf) + fread(buf, 1, IO_LEN, stdin);
if (ioh == iot) return -1;
}
return *ioh++;
}
template<class T>
inline void read(T &x) {
static char ioc;
static bool iosig = 0;
for (iosig = 0, ioc = read(); !isdigit(ioc); ioc = read()) if (ioc == '-') iosig = 1;
for (x = 0; isdigit(ioc); ioc = read()) x = (x << 1) + (x << 3) + (ioc ^ '0');
if (iosig) x = -x;
}
template<class T, size_t size>
struct MemoryPool {
T buf[size], *tail, *end;
MemoryPool() : tail(buf), end(buf + size) {}
inline T *alloc() { return tail != end ? tail++ : new T; }
inline void clear() { this->tail = buf; }
};
const int MAXN = 100100;
using namespace std;
const int MAXM = 3804000;
struct Node {
Node *lc, *rc;
int val;
inline void *operator new (size_t, Node *lc, Node *rc, const int val) {
static Node buf[MAXM], *tail = buf;
return tail->lc = lc, tail->rc = rc, tail->val = val, tail++;
}
inline Node *insert(const int l, const int r, const int pos, const int val) {
register int mid = l + r >> 1;
if (l == r) return new (0x0, 0x0, this->val + val) Node;
if (pos <= mid) return new (lc->insert(l, mid, pos, val), rc, this->val + val) Node;
else return new (lc, rc->insert(mid + 1, r, pos, val), this->val + val) Node;
}
inline friend int query(const Node *p1, const Node *p2, const Node *p3, const Node *p4, const int x, const int y, const int l, const int r) {
register int mid = x + y >> 1;
if (x == l && y == r) return p1->val + p2->val - p3->val - p4->val;
if (r <= mid) return query(p1->lc, p2->lc, p3->lc, p4->lc, x, mid, l, r);
if (l > mid) return query(p1->rc, p2->rc, p3->rc, p4->rc, mid + 1, y, l, r);
return query(p1->lc, p2->lc, p3->lc, p4->lc, x, mid, l, mid) + query(p1->rc, p2->rc, p3->rc, p4->rc, mid + 1, y, mid + 1, r);
};
}*tree[MAXN];
struct Query {
int x, y;
inline bool operator < (const Query &q) const { return x != q.x ? x < q.x : y < q.y; }
inline bool operator == (const Query &q) const { return x == q.x && y == q.y; }
} que[MAXN];
struct Edge {
int to;
Edge *next;
inline void init(const int to, Edge *next) { this->to = to, this->next = next; }
} edge[MAXN << 1];
Edge *head[MAXN], *cur = edge;
int n, m, fa[MAXN], dep[MAXN], ancestor[MAXN][18], in[MAXN], out[MAXN];
vector<int> g[MAXN];
long long A, B;
inline void addEdge(const int u, const int v) { (++cur)->init(v, head[u]), head[u] = cur; }
inline void dfs1(const int x) {
static int cnt;
dep[x] = dep[fa[x]] + 1, in[x] = ++cnt;
for (Edge *p = head[x]; p; p = p->next) if (p->to != fa[x]) fa[p->to] = x, ancestor[p->to][0] = x, dfs1(p->to);
out[x] = ++cnt;
}
inline void dfs2(const int x) {
tree[x] = tree[fa[x]];
for (std::vector<int>::iterator it = g[x].begin(); it != g[x].end(); it++)
tree[x] = tree[x]->insert(1, n << 1, in[*it], 1), tree[x] = tree[x]->insert(1, n << 1, out[*it], -1);
for (Edge *p = head[x]; p; p = p->next) if (p->to != fa[x]) dfs2(p->to);
}
inline int LCA(int x, int y) {
if (dep[x] < dep[y]) std::swap(x, y);
for (register int j = 17; ~j; j--) if (dep[ancestor[x][j]] >= dep[y]) x = ancestor[x][j];
if (x == y) return x;
for (register int j = 17; ~j; j--) if (ancestor[x][j] != ancestor[y][j]) x = ancestor[x][j], y = ancestor[y][j];
return fa[x];
}
int main() {
register int x, y;
read(n), read(m);
for (register int i = 1; i < n; i++) read(x), read(y), addEdge(x, y), addEdge(y, x);
for (register int i = 1; i <= m; i++) read(x), read(y), g[x].push_back(y), que[i].x = x, que[i].y = y;
tree[0] = new (0x0, 0x0, 0) Node, tree[0]->lc = tree[0]->rc = tree[0], dfs1(1), dfs2(1);
for (register int j = 1; j <= 17; j++)
for (register int i = 1; i <= n; i++)
ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];
for (register int i = 1; i <= m; i++) {
x = que[i].x, y = que[i].y;
register int lca = LCA(x, y);
A += query(tree[x], tree[y], tree[lca], tree[fa[lca]], 1, n << 1, in[lca], in[x]) + query(tree[x], tree[y], tree[lca], tree[fa[lca]], 1, n << 1, in[lca], in[y]) - query(tree[x], tree[y], tree[lca], tree[fa[lca]], 1, n << 1, in[lca], in[lca]) - 1;
}
std::sort(que + 1, que + m + 1);
register int i, j;
for (i = 1; i <= m; i = j) {
for (j = i + 1; j <= m && que[i] == que[j]; j++);
A -= (long long)(j - i) * (j - i - 1) >> 1;
}
B = (long long)m * (m - 1) >> 1;
long long gcd = std::__gcd(A, B);
A /= gcd; B /= gcd;
cout << A << '/' << B;
return 0;
}
分享到