POJ – 3417 Network 【樹上差分 LCA 思維】 好題!

NO IMAGE

傳送門
題意:

先給一棵具有n個節點的樹, 然後再給出m條邊, 問從樹上刪去一條邊, 再從m條邊中刪去一條邊, 把這個圖分成至少兩部分的方案數.

思路

我們知道再樹上每加一條邊樹上一定有環, 假設我們將在環上的樹邊的累加標記都加一, 表示被一條m中的邊所覆蓋, 然後我們在分析, 對於一顆樹我們刪去任意一條邊, 樹一定會被分成兩部分, 那麼如果被刪去的邊的累加標記>=2, 說明有>=2條m中的邊連線成環的樹邊中有它, 也就是樹分成的兩部分有至少2條邊還連線著, 這樣的話不管你怎麼選都不可能被劃分成兩部分, 方案數 0, 而被覆蓋了一次的了? 那就只能刪去讓它成環的那條邊, 方案數 1, 而覆蓋0次的最脆弱, 只要斷開它, 一定會有兩部分, 方案數 m, 所以做一次樹上的差分就好了, 統計好每條邊被覆蓋的次數, 然後對應的累加答案即可..

AC Ciode

const int maxn = 1e5   5;
int up[maxn][23];
int deep[maxn], dis[maxn];
int cnt, head[maxn];
int n, m, q;
struct node {
int to, next, w;
}e[maxn<<1];
void init() {
Fill(head,-1); Fill(dis,0);
Fill(up,0); Fill(deep,0);
cnt = 0;
}
void add(int u, int v, int w) {
e[cnt] = node{v, head[u], w};
head[u] = cnt  ;
}
void dfs(int u,int fa,int d) {
deep[u] = d   1;
for(int i = 1 ; i < 20 ; i   ) {
up[u][i] = up[up[u][i-1]][i-1];
}
for(int i = head[u] ; ~i ; i = e[i].next) {
int to = e[i].to;
if(to == fa) continue;
up[to][0] = u;
dfs(to, u, d 1);
}
}
int LCA_BZ(int u,int v) {
int mx = 0;
if(deep[u] < deep[v]) swap(u,v);
int k = deep[u] - deep[v];
for(int i = 19 ; i >= 0 ; i --) {
if((1<<i) & k) {
u = up[u][i];
}
}
if(u == v) return u;
for(int i = 19 ; i >= 0 ; i --) {
if(up[u][i] != up[v][i]){
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
ll ans;
ll dfs2(int u, int fa) {
int num = dis[u];
for (int i = head[u] ; ~i ; i = e[i].next) {
int to = e[i].to;
if (to == fa) continue;
num  = dfs2(to, u);
}
if (num < 2 && u != 1) {
if (num)    ans;
else ans  = m;
}
return num;
}
void solve() {
scanf("%d%d", &n, &m); init();
for (int i = 1 ; i < n ; i   ) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v, 1); add(v, u, 1);
}
dfs(1, -1, 0);
for (int i = 1 ; i <= m ; i   ) {
int u, v;
scanf("%d%d", &u, &v);
dis[u];    dis[v];
dis[LCA_BZ(u, v)] -= 2;
}
ans = 0; dfs2(1, -1);
printf("%lld\n", ans);
}