G8012 [GESP202503 八级] 割裂 题解

知识点：最近公共祖先、树上差分、路径覆盖。

解题思路

对每条被影响路径(u,v)做树上点差分：两端加1，LCA及LCA父亲各减1。后序累加得到每点被覆盖次数，最后沿询问路径统计覆盖数为0的节点。

为什么正确

点差分在路径分叉处抵消多余贡献，后序合并后仅保留位于指定路径上的增量，零覆盖恰为仍可选择的节点。

易错点

本题是点差分，不是只在LCA减2的边差分；LCA本身也要统计一次，根父亲用哨兵0。

复杂度

预处理O((n+a)log n)，最后单次路径统计O(n)上界，空间O(n log n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,a;
    cin>>n>>a;
    vector<vector<int>>g(n+1);
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>p(n+1),dep(n+1),order= {
        1
    }
    ;
    for(int k=0;k<(int)order.size();k++) {
        int u=order[k];
        for(int v:g[u])if(v!=p[u]) {
            p[v]=u;
            dep[v]=dep[u]+1;
            order.push_back(v);
        }
    }
    int L=1;
    while((1<<L)<=n)L++;
    vector<vector<int>>up(L,p);
    for(int k=1;k<L;k++)for(int i=1;i<=n;i++)up[k][i]=up[k-1][up[k-1][i]];
    auto lca=[&](int u,int v) {
        if(dep[u]<dep[v])swap(u,v);
        int dif=dep[u]-dep[v];
        for(int k=0;k<L;k++)if(dif>>k&1)u=up[k][u];
        if(u==v)return u;
        for(int k=L-1;k>=0;k--)if(up[k][u]!=up[k][v]) {
            u=up[k][u];
            v=up[k][v];
        }
        return p[u];
    }
    ;
    vector<int>diff(n+1);
    while(a--) {
        int u,v;
        cin>>u>>v;
        int z=lca(u,v);
        diff[u]++;
        diff[v]++;
        diff[z]--;
        diff[p[z]]--;
    }
    for(int k=n-1;k>0;k--)diff[p[order[k]]]+=diff[order[k]];
    int u,v;
    cin>>u>>v;
    int z=lca(u,v),ans=0;
    while(u!=z) {
        ans+=diff[u]==0;
        u=p[u];
    }
    while(v!=z) {
        ans+=diff[v]==0;
        v=p[v];
    }
    ans+=diff[z]==0;
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用20个自行生成的测试点。