题解：P11967 [GESP202503 八级] 割裂

shuqiang · 2025-04-01 22:56:53 · 题解

八级最简单的一次考试。

我们来看这棵树，假设好点对是 (4,6)，那么删除其中 4,2,1,3,6 都不符合题意，观察这个结果，发现这个其实就是这棵树上的路径。

但是，这题最多有 10^5 个点对，一个一个枚举肯定是不行的，其实这里只需要统计每一个点有没有被一个好点对的路径经过，考虑用树上差分，假设我们要加入好点对 (4,5)，那么我们在点 4,5 标记加 1，然后此时 2 实际被统计了两次，所以标记 2 减 1，然后 2 上面是没有被经过的，所以令 2 的父亲节点减 1。

此时标记如下：

标记完了后我们就统计每个子树内的节点和，最终就变成这个样子：

这样，每个点对只作 4 次标记，总时间复杂度 \mathcal{O}(n \log n+a)。

#include<iostream>
#include<vector>

using namespace std;

const int N = 1e6 + 10;
int n, q, u, v, a[N], fa[N][20], dep[N], cnt;
vector<int> g[N];

void dfs(int u, int f){
    fa[u][0] = f;
    dep[u] = dep[f] + 1;
    for(int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i-1]][i-1];
    for(int v: g[u]){
        if(v == f) continue;
        dfs(v, u);
    }
}

int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 19; i >= 0; i--){
        if((dep[u] - dep[v]) & (1 << i)) u = fa[u][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--){
        if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    }
    return fa[u][0];
}

void get_ans(int u, int f){
    for(int v: g[u]){
        if(v == f) continue;
        get_ans(v, u);
        a[u] += a[v];
    }
}

int main(){
    cin >> n >> q;
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    while(q--){
        cin >> u >> v;
        int w = lca(u, v);
        a[u]++; a[v]++;
        a[w]--; a[fa[w][0]]--;
    }
    get_ans(1, 0);
    cin >> u >> v;
    int w = lca(u, v);
    while(u != w){
        if(a[u] == 0) cnt++;
        u = fa[u][0];
    }
    while(v != w){
        if(a[v] == 0) cnt++;
        v = fa[v][0];
    }
    if(a[u] == 0) cnt++;
    cout << cnt;
    return 0;
}