暗的连锁

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1676 字
N个点，N-1条主要边与M条附加边。先斩一条
一本通
例
正文

/*
原题：T1553 「一本通 4.4 例 2」暗的连锁 (POJ 3417)
题意：N 个点，N-1 条主要边（构成树）与 M 条附加边。先斩一条主要边再斩一条附加边，求使图不连通的方案数。
思路：每条附加边 (u,v) 在树上差分：cnt[u]++, cnt[v]++, cnt[lca(u,v)]-=2；子树和即覆盖该父子边的主要边数 k。k=0 方案数 M，k=1 方案数 1，k>=2 方案数 0。
复杂度：O((N+M) log N)。
易错点：差分后自下而上累加得到的是“边 (v,父亲)”被覆盖次数；答案为所有非根节点的贡献之和。
*/
#include <bits/stdc++.h>
using namespace std;
const int LOG=20;
int n,m;
vector<vector<int>> g;
vector<int> dep;
vector<vector<int>> up;
vector<long long> cnt;
void dfs(int u,int p){
    up[u][0]=p;
    for(int i=1;i<LOG;i++) up[u][i]=up[up[u][i-1]][i-1];
    for(int v:g[u]){
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LOG-1;i>=0;i--)
        if(dep[x]-(1<<i)>=dep[y]) x=up[x][i];
    if(x==y) return x;
    for(int i=LOG-1;i>=0;i--)
        if(up[x][i]!=up[y][i]){ x=up[x][i]; y=up[y][i]; }
    return up[x][0];
}
void dfs2(int u,int p){
    for(int v:g[u]){
        if(v==p) continue;
        dfs2(v,u);
        cnt[u]+=cnt[v];
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    g.assign(n+1,vector<int>());
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dep.assign(n+1,0);
    up.assign(n+1,vector<int>(LOG,0));
    dfs(1,0);
    cnt.assign(n+1,0);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        int l=lca(u,v);
        cnt[u]++;
        cnt[v]++;
        cnt[l]-=2;
    }
    dfs2(1,0);
    long long ans=0;
    for(int v=2;v<=n;v++){
        if(cnt[v]==0) ans+=m;
        else if(cnt[v]==1) ans+=1;
    }
    cout<<ans<<'\n';
    return 0;
}
暗的连锁

正文

一本通·提高篇的其它内容
