题目链接

解题思路

请见李煜东的蓝书，里面的讲解比任何博客都好。

说白了就是一个“覆盖”，然后用树上查分O(1)维护树上边被覆盖的次数，以点代边，边所连的子节点作为这条边的“配套点”。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int head[100005];
struct e{
    int nxt,to;
}edge[200005];
int tot=0;
void add_edge(int u,int v){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].to=v;
    head[u]=tot;
}
int father[30][100005];
int depth[100005];
int logg;
int num[100005];
void DFS(int now,int f,int d){
    father[0][now]=f;
    depth[now]=d;
    for(int i=head[now];i;i=edge[i].nxt){
        if(edge[i].to!=f){
            DFS(edge[i].to,now,d+1);
        }
    }
    
}
void init(){
    DFS(1,-1,1);
    for(int i=1;i<=logg;i++){
        for(int j=1;j<=n;j++){
            father[i][j]=father[i-1][father[i-1][j]];
        }
    }
}
int LCA(int a,int b){
    if(depth[a]<depth[b])swap(a,b);//a深度比b大 
    for(int i=logg;i>=0;i--){
        if(depth[father[i][a]]>=depth[b]){
            a=father[i][a];
        }
    }
    if(a==b){
        return a;
    }
    for(int i=logg;i>=0;i--){
        if(father[i][a]!=father[i][b]){
            a=father[i][a],b=father[i][b];
        }
    }
    return father[0][a];
}
int sum[100005];
int dfs(int now,int f){
    sum[now]=0;
    int cnt=0;
    for(int i=head[now];i;i=edge[i].nxt){
        cnt++;
        if(edge[i].to!=f){
            sum[now]+=dfs(edge[i].to,now);
        }
    }
    sum[now]+=num[now];
    return sum[now];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        sum[i]=-1;
    }
    logg=log2(n)+1;
    int u,v;
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    init();
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        num[u]++;
        num[v]++;
        num[LCA(u,v)]-=2; 
    }
    int tmp=dfs(1,-1);
    sum[1]=-1;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(sum[i]==0){
            ans+=m;
        }else if(sum[i]==1){
            ans+=1;
        }
    }
    printf("%d",ans);
    return 0;
}

本文链接：http://kaispace.com.cn/index.php/archives/731/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者