<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
倍增+树上差分
虽然同为困难,但显然它并没有次小生成树复杂,不需要像次小生成树那样从头到尾写满详细注释才能避免被绕晕,与此相对应的,文档部分会写的更加详细
由于图结构中不存在重边,因此任意一条次要边(非树边)都会和一些主要边(树边)形成环,相当于这些树边都会被某条非树边“关联”一次,确定哪些边被关联,就相当于对每条非树边的两个端点,求它们之间连通的路径,树结构中这个路径可以通过求最近公共祖先得知
接下来就是分几种情况来考虑:
黑色和绿色为树边,红色为非树边,绿色代表选定要切掉的树边,被关联的次数分别为0,1,2
最左边的情况,切掉绿色边,就已经可以使得图不连通了,3条红色边可以任意切
中间的情况,切掉绿色边后图仍然连通,那么必须切断那条红色边才能使图不连通
最右边的情况,切掉绿色边后,无论切哪条红色边,在只切一条红色边的情况下,图始终连通
所以最重要的一步就是求出每条边被关联了几次,借助LCA,可以使用树上差分法,然后求前缀和统计边权,累加方案数,详情请见注释
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 5, M = 2 * N, maxPower = 17;
using ll = long long;
int n, m;//树边和非树边的数量
int fin[M], nxt[M], last[N], tot = 2;//链式前向星用
int depth[N], val[N];//深度,权值
int pre[N][maxPower];//(i,j)记录从i节点向上倍增j次(移动2^j层)到达的节点
queue<int> q;//确定深度的时候用
ll ans = 0ll;//确定最终结果
//连接一条树边
void _connect(int s, int e);//单向
void connect(int s, int e);//双向
//求深度,初始化pre表
void setDepth(int root);
//求最近公共祖先
int lca(int s, int e);
//统计方案数
ll dfs(int cur, int prev = -1);
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
//树边,需要在图结构中连上
for (int i = 1; i < n; i++) {
int s, e;
cin >> s >> e;
connect(s, e);
}
//任选一个节点作为根
setDepth(1);
//非树边,可以联机查询,不用连到图里
for (int i = 0; i < m; i++) {
int s, e;
cin >> s >> e;
//一条非树边连上后必成环
//要做的就是给环上每条树边的权值都加1
//可以用树上差分
val[s]++;
val[e]++;
int a = lca(s, e);
val[a] -= 2;
}
//根节点必须和求深度时的根节点保持一致
dfs(1);
cout << ans << endl;
return 0;
}
void _connect(int s, int e)
{
fin[tot] = e;
nxt[tot] = last[s];
last[s] = tot++;
}
void connect(int s, int e)
{
//无向边可以看作两条方向相反的有向边
_connect(s, e);
_connect(e, s);
}
//基于BFS求深度,每确定一个节点i的深度就倍增上移初始化pre[i]
void setDepth(int root)
{
fill(depth, depth + N, 1e9 + 7);
depth[0] = 0;
depth[root] = 1;
q.push(root);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = last[cur]; i != 0; i = nxt[i]) {
int nx = fin[i];
if (depth[nx] > depth[cur] + 1) {
depth[nx] = depth[cur] + 1;
q.push(nx);
pre[nx][0] = cur;
for (int j = 1; j < maxPower; j++) {
pre[nx][j] = pre[pre[nx][j - 1]][j - 1];
}
}
}
}
}
//构造差分序列有用
int lca(int s, int e)
{
if (depth[s] < depth[e]) swap(s, e);
//先让s,e同深度
for (int i = maxPower - 1; i >= 0; i--) {
if (depth[pre[s][i]] >= depth[e]) {
s = pre[s][i];
}
}
if (s == e) return s;
//再让s,e一起倍增
for (int i = maxPower - 1; i >= 0; i--) {
if (pre[s][i] != pre[e][i]) {
s = pre[s][i];
e = pre[e][i];
}
}
return pre[s][0];
}
//遍历统计的同时,求前缀和得到原序列
ll dfs(int cur, int prev)
{
ll res = val[cur];
for (int i = last[cur]; i != 0; i = nxt[i]) {
int nx = fin[i];
if (nx == prev) continue;
//后序遍历,先统计子树的信息
ll child = dfs(nx, cur);//得到的其实是(cur,nx)这条边被非树边关联的次数
if (child == 0) ans += m;//没有被关联过,只要切了它就能干掉Dark,然后再切任意一条非树边
else if (child == 1) ans++;//被关联了一次,切了它之后必须切掉关联它的特定非树边
//如果一条边被关联超过1次,那么就算切掉了它,也不可能只切一条非树边就干掉Dark
res += child;//子树中的值加到当前节点中
}
return res;
}