【BZOJ3772】精神污染
wangyuchen
2018-06-07 18:45:34
## 题目 ##
[传送门](https://www.lydsy.com/JudgeOnline/problem.php?id=3772)
## 题解&算法 ##
看完题后千万不要被概率吓到
这题的难点在于求与一条路径被另一条路径包含的总数量
很明显如果以x,a被x,b包含， 那么$in[b] <= in[a] < out[b]$， 且$out[a] > out[b]$
于是我们可以用主席树来处理一下， 建树时差分一下， 查询时也是前缀和差分
## 代码 ##
```cpp
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200010;
typedef long long LL;
struct edge
{ int from, to;
edge() { }
edge(int _1, int _2) : from(_1), to(_2) { }
} edges[M];
int head[N], nxt[M], tot;
inline void init()
{ memset(head, -1, sizeof(head));
tot = 0;
}
inline void add_edge(int x, int y)
{ edges[tot] = edge(x, y);
nxt[tot] = head[x];
head[x] = tot++;
edges[tot] = edge(y, x);
nxt[tot] = head[y];
head[y] = tot++;
}
int dep[N], father[N][17];
int in[N], out[N], dfs_clock;
void dfs(int x)
{ for (int i = 1; (1<<i) <= dep[x]; i++)
father[x][i] = father[father[x][i-1]][i-1];
in[x] = ++dfs_clock;
for (int i = head[x]; ~i; i = nxt[i])
{ edge & e = edges[i];
if (e.to != father[x][0])
{ dep[e.to] = dep[x] + 1;
father[e.to][0] = x;
dfs(e.to);
}
}
out[x] = ++dfs_clock; //少了++样例输出就变成-1/1了
}
int getLCA(int x, int y)
{ if (dep[x] > dep[y]) swap(x, y);
int d = dep[y] - dep[x];
for (int i = 0; (1<<i) <= d; i++)
if (d & (1<<i)) y = father[y][i];
if (x == y) return x;
for (int i = 16; i >= 0; i--)
{ if (father[x][i] != father[y][i])
{ x = father[x][i];
y = father[y][i];
}
}
return father[x][0];
}
int root[N * 2];
struct SegmentTree
{ int ls[3800010], rs[3800010], sz;
int sumv[3800010];//开40000010会MLE
inline void cpynode(int x, int y)
{ ls[x] = ls[y];
rs[x] = rs[y];
sumv[x] = sumv[y];
}
void insert(int & cur, int pre, int l, int r, int p, int val)
{ cur = ++sz;
cpynode(cur, pre);
sumv[cur] += val;
if (l == r) return;
int mid = (l + r) >> 1;
if (p <= mid)
insert(ls[cur], ls[pre], l, mid, p, val);
else
insert(rs[cur], rs[pre], mid+1, r, p, val);
}
LL query(int x, int y, int z, int k, int l, int r, int ql, int qr)
{ if (ql == l && qr == r)
return sumv[x] + sumv[y] - sumv[z] - sumv[k];
int mid = (l + r) >> 1;
if (qr <= mid)
return query(ls[x], ls[y], ls[z], ls[k], l, mid, ql, qr);
else if (ql > mid)
return query(rs[x], rs[y], rs[z], rs[k], mid+1, r, ql, qr);
else
return query(ls[x], ls[y], ls[z], ls[k], l, mid, ql, mid) +
query(rs[x], rs[y], rs[z], rs[k], mid+1, r, mid+1, qr);
}
} st;
LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); }
int n, m;
struct Data
{ int x, y;
Data() { }
Data(int _1, int _2) : x(_1), y(_2) { }
} L[N];
bool cmp(Data a, Data b) { return a.x != b.x ? a.x < b.x : a.y < b.y; }
vector<int> vec[N];
void dfs_2(int x)
{ root[x] = root[father[x][0]];
for (int i = 0; i < vec[x].size(); i++)
st.insert(root[x], root[x], 1, dfs_clock, in[vec[x][i]], 1),
st.insert(root[x], root[x], 1, dfs_clock, out[vec[x][i]], -1);
for (int i = head[x]; ~i; i = nxt[i])
{ edge & e = edges[i];
if (e.to != father[x][0])
dfs_2(e.to);
}
}
int main()
{ scanf("%d %d", &n, &m);
init();
for (int i = 1; i < n; i++)
{ int x, y;
scanf("%d %d", &x, &y);
add_edge(x, y);
}
father[1][0] = 0;
dep[1] = 1;
dfs(1);
for (int i = 1; i <= m; i++)
scanf("%d %d", &L[i].x, &L[i].y),
vec[L[i].x].push_back(L[i].y);
dfs_2(1);
sort(L + 1, L + m + 1, cmp);
LL ans1 = 0, ans2 = (LL) m * (m-1) / 2;
for (int i = 1; i <= m; i++)
{ int lca = getLCA(L[i].x, L[i].y);
ans1 += st.query(root[L[i].x], root[L[i].y], root[lca], root[father[lca][0]], 1, dfs_clock, in[lca], in[L[i].x]) +
st.query(root[L[i].x], root[L[i].y], root[lca], root[father[lca][0]], 1, dfs_clock, in[lca], in[L[i].y]) - //刚开始减号打成加号调了很久啊。。。
st.query(root[L[i].x], root[L[i].y], root[lca], root[father[lca][0]], 1, dfs_clock, in[lca], in[lca])
- 1;
}
int j;
for (int i = 1; i <= m; i = j)
for (j = i; L[i].x == L[j].x && L[i].y == L[j].y; j++)
ans1 -= (LL) (j - i) * (j - i - 1) / 2//一定要减掉重复！！！！！！！！！！！！！
LL d = gcd(ans1, ans2);
ans1 /= d, ans2 /= d;
printf("%lld/%lld", ans1, ans2);
return 0;
}
```
## 恶心的地方 ##
1. 卡空间
2. 路径有重复