Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define N 200200
using namespace std;

int n,m,h[N],p[N],re,lab[N];
vector < int > a[N];

void init(int x)
{
    int i,y;
    fr(i,0,int(a[x].size())-1)
    {
        y=a[x][i];
        if (y==p[x]) continue;
        h[y]=h[x]+1; p[y]=x;
        init(y);
    }
}

int get(int x)
{
    if (lab[x]!=x) lab[x]=get(lab[x]);
    return lab[x];
}

void go(int X,int Y)
{
    int x=X,y=Y;
    while (x!=y)
    {
        x=get(x); y=get(y);
        if (x==y) break;
        int hx=h[x], hy=h[y];
        if (hx<=hy) y=lab[y]=p[y], re--;
        if (hy<=hx) x=lab[x]=p[x], re--;
    }
}

int main()
{
    int i,x,y;
    cin >> n;
    fr(i,2,n)
    {
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    init(1);
    re=n-1;
    fr(i,1,n) lab[i]=i;
    cin >> m;
    fr(i,1,m) 
    {
        scanf("%d%d",&x,&y);
        go(x,y);
    }
    cout << re << endl;
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>
#include <sstream>
#include <iomanip>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading


int n, h[200111], father[22][200111], f[200111];
vector<int> ke[200111];
int first, last, qu[200111];

void dfs(int u, int fu) {
    first = last = 1;
    qu[1] = u;
    h[1] = 1;

    while (first <= last) {
        int u = qu[first++];
        REP(i,ke[u].size()) {
            int v = ke[u][i];
            if (!h[v]) {
                h[v] = h[u] + 1;
                father[0][v] = u;
                qu[++last] = v;
            }
        }
    }
}

void init() {
    FOR(i,1,18)
    FOR(u,1,n) {
        int v = father[i-1][u];
        if (v == -1) father[i][u] = -1;
        else father[i][u] = father[i-1][v];
    }
}

void lca(int u, int v) {
    ++f[u]; ++f[v];
    if (h[u] < h[v]) swap(u, v);
    if (h[u] != h[v]) {
        int need = h[u] - h[v];
        FORD(i,18,0) if (need & (1<<i)) {
            u = father[i][u];
        }
    }

    if (u != v) {
        FORD(i,18,0) if (father[i][u] != father[i][v]) {
            u = father[i][u];
            v = father[i][v];
        }
        u = father[0][u];
    }
    f[u] -= 2;
}

int main() {
    GN(n);
    FOR(i,2,n) {
        int u, v;
        GN(u); GN(v);
        ke[u].PB(v);
        ke[v].PB(u);
    }
    memset(father, -1, sizeof father);
    dfs(1, -1);
    init();
    int q; GN(q);
    int u, v;
    while (q--) {
        GN(u); GN(v);
        lca(u,v);
    }

    int res = 0;

    FORD(t,n,2) {
        u = qu[t];
        REP(i,ke[u].size()) {
            v = ke[u][i];
            if (v != father[0][u])
                f[u] += f[v];
        }
        if (!f[u]) ++res;
    }

    cout << res << endl;
    return 0;
}