题解：B4339 [中山市赛 2023] 树的改造

gitxiaozheng · 2026-07-23 22:13:50 · 题解

本题重在转化题意。

容易观察到一个事实：对于给出的 B 树边 (u,v)，当 A 树不存在 (u,v) 这条边的时候，我们只需想办法去掉 u \rightarrow v 这条路径上的点，然后直接在 u 和 v 之间建一条边就可以了。

这按照题目的意思，就是把这些点全部打上魔法标记，断开这些点的邻边后直接建一条边将 u 和 v 连起来。

综上，我们要统计的就是这些被打上魔法标记的点有多少个。

如果我们把给出的 B 树边 (u,v) 看作 A 树的树上路径，这题就转化成了：

给定 m 条树上路径 (u,v)，统计所有路径经过点（不含 u 和 v）的个数之和。有多条路径经过的点只算一次。

显然要用到树上差分中的点差分，于是这题迎刃而解。

::::info[实现细节]

然而不能直接抄了点差分的代码，毕竟还是有一点点不同。

首先是经过的点不含路径端点，而点差分的模板是包含路径端点的。与其他题解不同的是，我选择了一种不太需要动脑的方式：先跑一遍模板点差分，然后再统一将路径端点的贡献减去，具体看代码。
然后是有多条路径经过的点只算一次。这个不难实现，只需要在减去路径端点贡献后，统计被经过次数 >0 的点的个数即可。

::::

::::success[AC code & 提交记录]

//edit by devc++
//by gitxiaozheng/dakada
#include<bits/stdc++.h>
using namespace std;
#define L long long
#define iotype L  
#define space putchar(' ')
#define enter putchar('\n')
inline iotype qcin();
void qcout(iotype);
const int maxn=1e6+10;
int dfn[maxn],timed=0;

vector<int> Tree[maxn];
vector<pair<int,int>> edges;//记录一下各边，为日后减去端点贡献做准备

int ST[maxn][20];
int diff[maxn],Ans[maxn],fa[maxn];

void addedge(int u,int v){
    Tree[u].push_back(v);
    Tree[v].push_back(u);
}   
int ge(int u,int v){return dfn[u]<dfn[v]?u:v;}
void dfs(int u,int U){
    dfn[u]=++timed;
    fa[u]=ST[dfn[u]][0]=U;
    for(int to:Tree[u]){
        if(to!=U){
            dfs(to,u);
        }
    }
}
void predone(int n,int s){
    dfs(s,0);
    for(int j=1;j<=log2(n);j++){
        for(int i=1;i<=n-(1<<(j-1))+1;i++)
            ST[i][j]=ge(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
    }
}
int query(int l,int r){
    int k=log2(r-l+1);
    return ge(ST[l][k],ST[r-(1<<k)+1][k]);
}
int lca(int u,int v){
    if(u==v){
        return u;
    }
    if(dfn[u]>dfn[v]){
        swap(u,v);
    }
    return query(dfn[u]+1,dfn[v]);
}

void calc(int u,int U){
    Ans[u]=diff[u];
    for(int to:Tree[u]){
        if(to!=U){
            calc(to,u);
            Ans[u]+=Ans[to];
        }
    }
}

int main(){
    //Your code is here...
    int n=qcin(),s=1;
    for(int i=1;i<=n-1;i++){
        int u=qcin(),v=qcin();
        addedge(u,v);
    }

    predone(n,s);
    for(int i=1;i<=n-1;i++){
        int u=qcin(),v=qcin();
        diff[u]+=1;
        diff[v]+=1;
        diff[lca(u,v)]-=1;
        if(fa[lca(u,v)]!=0){
            diff[fa[lca(u,v)]]-=1;
        }
        edges.push_back(make_pair(u,v));
    }
    calc(s,0);

    for(auto ed:edges){
        //这里直接减去各端点贡献
        Ans[ed.first]--;
        Ans[ed.second]--;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=(Ans[i]>0);
    }
    qcout(ans);
    return 0;
}

inline iotype qcin(){
    iotype k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        k=k*10+c-'0';
        c=getchar();
    }
    return k*f;
}
void qcout(iotype x){
    static int num[20];
    int tot=0;
    if(x<0){
        putchar('-');
        x=-x;
    }
    while(x>=10){
        num[++tot]=x%10;
        x/=10;
    }
    putchar(x+'0');
    for(int i=tot;i>=1;i--){
        putchar(num[i]+'0');
    }
}

这是提交记录。