352. 闇の連鎖 - AcWing題庫

傳說中的暗之連鎖被人們稱為 Dark。

Dark 是人類內(nèi)心的黑暗的產(chǎn)物，古今中外的勇者們都試圖打倒它。

經(jīng)過研究，你發(fā)現(xiàn) Dark 呈現(xiàn)無向圖的結(jié)構(gòu)，圖中有?N?個(gè)節(jié)點(diǎn)和兩類邊，一類邊被稱為主要邊，而另一類被稱為附加邊。

Dark 有?N–1 條主要邊，并且 Dark 的任意兩個(gè)節(jié)點(diǎn)之間都存在一條只由主要邊構(gòu)成的路徑。

另外，Dark 還有?M?條附加邊。

你的任務(wù)是把 Dark 斬為不連通的兩部分。

一開始 Dark 的附加邊都處于無敵狀態(tài)，你只能選擇一條主要邊切斷。

一旦你切斷了一條主要邊，Dark 就會進(jìn)入防御模式，主要邊會變?yōu)闊o敵的而附加邊可以被切斷。

但是你的能力只能再切斷 Dark 的一條附加邊。

現(xiàn)在你想要知道，一共有多少種方案可以擊敗 Dark。

注意，就算你第一步切斷主要邊之后就已經(jīng)把 Dark 斬為兩截，你也需要切斷一條附加邊才算擊敗了 Dark。

輸入格式

第一行包含兩個(gè)整數(shù)?N?和?M。

之后?N–1 行，每行包括兩個(gè)整數(shù)?A?和?B，表示?A?和?B?之間有一條主要邊。

之后?M?行以同樣的格式給出附加邊。

輸出格式

輸出一個(gè)整數(shù)表示答案。

數(shù)據(jù)范圍

N≤100000,M≤200000，數(shù)據(jù)保證答案不超過2^31?1

輸入樣例：

4 1
1 2
2 3
1 4
3 4

輸出樣例：

3

解析：?

”主要邊“構(gòu)成一棵樹，”附加邊“則是”非樹邊“。把一條附加邊（x，y）添加到主要邊構(gòu)成的樹中，會與樹上 x，y 之間的路徑形成一個(gè)環(huán)。如果第一步選擇切斷 x，y 之間路徑上的某條邊，那么第二步就必須切斷附加邊（x，y），才能令dark被斬為不連通的兩部分。

因此，我們稱每條附加邊（x，y）都把樹上 x，y 之間的路徑上的每條邊“覆蓋了一次”。我們只需要統(tǒng)計(jì)出每條“主要邊”被覆蓋了多少次。若第一步把被覆蓋0次的主要邊切斷，則第二步可以任意切斷一條附加邊。若第一次把覆蓋1次的主要邊切斷，則第二步只能切斷一條附加邊。若第一次把覆蓋2次及2次以上的主要邊切斷，則第二步怎么且都不能滿足題意。據(jù)此我們可以統(tǒng)計(jì)出所有的方案數(shù)。

綜上所述，下面我們要解決的問題模型是：給定一張無向圖和一棵生成樹，求每條“樹邊”被“非樹邊”覆蓋了多少次。

解決此問題的經(jīng)典做法就是“樹上差分”。我們給樹上每個(gè)節(jié)點(diǎn)一個(gè)初始為0的權(quán)值，然后對每條非樹邊（x，y），令節(jié)點(diǎn) x 的權(quán)值加1，節(jié)點(diǎn) y 的權(quán)值加1，節(jié)點(diǎn) LCA（x，y）的權(quán)值減2。最后對這棵生成樹進(jìn)行一次深度優(yōu)先遍歷，求出 F[x] 表示以 x 為根的子樹中各節(jié)點(diǎn)的權(quán)值之和。F[x] 就是 x 與它的父節(jié)點(diǎn)之間的“樹邊”被覆蓋的次數(shù)。時(shí)間復(fù)雜度為 O（N+M）。

?

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, M = 2e5 + 5, INF = 0x3f3f3f3f;
int n, m;
int h[N], e[M], ne[M], idx;
int depth[N],fa[N][17],d[N];
int q[N];
int ans;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void bfs() {int hh = 0, tt = 0;memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[1] = 1;q[tt++] = 1;while (hh != tt) {int t = q[hh++];if (hh == N)hh = 0;for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (depth[j] > depth[t] + 1) {depth[j] = depth[t] + 1;q[tt++] = j;if (tt == N)tt = 0;fa[j][0] = t;for (int k = 1; k <= 16; k++) {fa[j][k] = fa[fa[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[fa[a][k]] >= depth[b])a = fa[a][k];}if (a == b)return a;for (int k = 16; k >= 0; k--) {if (fa[a][k] != fa[b][k]) {a = fa[a][k];b = fa[b][k];}}return fa[a][0];
}int dfs(int u,int father){int ret = d[u];for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j != father) {int s = dfs(j, u);if (!s)ans += m;else if (s == 1)ans++;ret += s;}}return ret;
}int main() {cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1,a,b,c; i < n; i++) {scanf("%d%d", &a, &b);add(a, b), add(b, a);}bfs();for (int i = 1,a,b; i <= m; i++) {scanf("%d%d", &a, &b);int p = lca(a, b);d[a]++, d[b]++, d[p] -= 2;}dfs(1,-1);cout << ans << endl;return 0;
}