倍增最小公共祖先LCA 差分区间修改求和 DFS BFS T4 352. 闇の連鎖 - AcWing题库 传说中的暗之连锁被人们称为 Dark。
Dark 是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。
经过研究，你发现 Dark 呈现无向图的结构，图中有 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。
Dark 有 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。
另外，Dark 还有 条附加边。
你的任务是把 Dark 斩为不连通的两部分。
一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。
一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。
但是你的能力只能再切断 Dark 的一条附加边。
现在你想要知道，一共有多少种方案可以击败 Dark。
注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。
输入格式
第一行包含两个整数 和 。
之后 行，每行包括两个整数 和 ，表示 和 之间有一条主要边。
之后 行以同样的格式给出附加边。
输出格式
输出一个整数表示答案。
数据范围
，数据保证答案不超过
输入样例：
4 1
1 2
2 3
1 4
3 4输出样例：
3思路
给 个节点和两类边, 第一类共 条, 且任意两个节点之间都存在一条路径, 也就构成了一个树。第二类共 条, 是附加边, 也就是非树边。
让求把该图通过切断一条树边和一条非树边, 使其不连通。输出所有方案数。
绿色为树边, 蓝色为非树边。可以知道, 所有的蓝色边要么和绿色边重合, 要么就与绿色边构成一个回路（重合也可以看做两个点的回路）。如图中存在一个回路。若要把该图变为非连通图, 可以切断右边两个非回路的树边, 或者左边回路中切任意一个树边并再切一个非树边。
若再增加一条非树边（如图）, 一种选择是切6号边, 或者切3,5,4号然后切一个非树边, 或者切1,2号点然后切两个非树边。若把每个树边切了之后还需要切几条非树边统计一下标到图上：
可以发现每多在一个回路中时, 需要切的非树边就多一个。那可以维护每个非树边的需切数量, 将只需要切0个和1个的累加就能得到答案。
在枚举非树边的时候, 每构成一个回路, 就要把回路中的点+1, 对于区间修改求和, 有个基础算法差分, 在 上 对应到树中就是：
- 在 节点
- 在 节点
- 在 节点 , 其中 为 的最小公共祖先
这样首先保证了在 子树之外的点不会受影响, 因为 和 抵消。而每个点的权值代表其连接父节点向上走的边的权值, 等于其子树节点权值之和。 这样就可以用 的复杂度统计差分, 最后再用 的复杂度 DFS 求子树之和。同时求解答案。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int cnt[M];
int depth[N], f[N][17];
int n,m;
int q[N];
int ans;
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
void bfs()
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[1] = 1;
int hh = 0, tt = 0;
q[0] = 1;
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t]; ~i ; i = ne[i])
{
int j = e[i];
if(depth[j] > depth[t] + 1)
{
q[++tt] = j;
depth[j] = depth[t] + 1;
f[j][0] = t;
for(int k = 1; k <= 16; k++)
f[j][k] = f[f[j][k-1]][k-1];
}
}
}
}
int lca(int a, int b)
{
if(depth[a] < depth[b]) swap(a,b);
for(int k = 16; k >= 0; k--)
if(depth[f[a][k]] >= depth[b])
a = f[a][k];
if(a == b) return a;
for(int k = 16; k >= 0; k--)
if(f[a][k] != f[b][k])
a = f[a][k], b = f[b][k];
return f[a][0];
}
int dfs(int u, int fa)
{
int res = cnt[u];
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
int s = dfs(j, u);
if(s == 0) ans += m;
else if(s == 1) ans++;
res += s;
}
return res;
}
int main()
{
memset(h , -1, sizeof h);
cin >> n >> m;
for(int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
add(a,b), add(b,a);
}
bfs();
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
int p = lca(a,b);
cnt[a]++, cnt[b]++, cnt[p] -= 2;
}
dfs(1,-1);
cout << ans << endl;
return 0;
}