题解 | 算法竞赛进阶指南 闇の連鎖

思路

删去一条树边能把树断成两个联通块.未删去的非树边不能把两个连通块再连回去(否则不是白搭了2333).
如果一条非树边与树上的边构成一个环,删去这个环的树边的同时,必须将这两条边同时删去.如果某条树边同时在好几个环中,肯定不能删去这条树边,因为只能删一条非树边,删了条非树边,剩下的还是连通.
对于一条非树边,原树上至的路径所有树边都覆盖一次(这些边能与非树边构成一个环),只覆盖过一次或一次都没有的树边才有可能删去,删去覆盖过一次的树边只能删去与其构成环的非树边,删去没覆盖过的树边再删去任何一条非树边都没问题.
所以说,只要计算每一条树边被覆盖了几次就OK了.
暴力计算需要的复杂度,用树前缀和计算就可以做到,其中是树上倍增的复杂度.

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define MAXN 100005
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
#define getchar() ( p1 == p2 && ( p1 = bf, p2 = bf + fread( bf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1++ )
char bf[1 << 21], *p1(bf), *p2(bf);
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
    for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
    for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}

clock_t t_bg, t_ed;

int N, M, hd[MAXN], nxt[MAXN<<1], to[MAXN<<1], tot;
inline void addedge( int x, int y ){
    nxt[++tot] = hd[x], hd[x] = tot, to[tot] = y,
    nxt[++tot] = hd[y], hd[y] = tot, to[tot] = x;
} int dep[MAXN], f[MAXN][20];
int LCA( int x, int y ){
    if ( dep[x] < dep[y] ) x^=y^=x^=y;
    fd( i, 18, 0 ) if ( dep[f[x][i]] > dep[y] ) x = f[x][i];
    if ( dep[x] > dep[y] ) x = f[x][0];
    fd( i, 18, 0 ) if ( f[x][i] != f[y][i] ) x = f[x][i], y = f[y][i];
    return x == y ? x : f[x][0];
}
void DFS( int u ){
    dep[u] = dep[f[u][0]] + 1;
    fp( i, 1, 18 ) f[u][i] = f[f[u][i - 1]][i - 1];
    go( i, hd[u] ) if ( v != f[u][0] )
        f[v][0] = u, DFS(v);
} int s[MAXN], ans;
void dfs( int u ){
    go( i, hd[u] ) if ( v != f[u][0] )
        dfs(v), s[u] += s[v];
    if ( u > 1 && s[u] == 1 ) ++ans;
    else if ( u > 1 && !s[u] ) ans += M;
}

int main(){
    t_bg = clock();
    read(N), read(M); int x, y;
    fp( i, 1, N - 1 ) read(x), read(y), addedge( x, y );
    DFS(1); fp( i, 1, M ) read(x), read(y), ++s[x], ++s[y], s[LCA(x, y)] -= 2;
    dfs(1), printf( "%d\n", ans );
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}