C++14(g++5.4) 解法, 执行用时: 171ms, 内存消耗: 13788K, 提交时间: 2020-01-26 21:51:22

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100100;
int fa[N],dp[N],n,m;
vector<int> G[N],q[N];

int v[N];
ll ans;
int get(int x) {
    if(x==fa[x]) return x;
    else return fa[x] = get(fa[x]);
}

void tarjan(int x) {
    v[x] = 1;

    for(auto y:G[x]) {
        if(v[y]) continue;
        tarjan(y);
        fa[y] = x;
    }
    for(auto y:q[x]) {
        if(v[y]==2) {
            int lca = get(y);
            dp[x]++, dp[y]++, dp[lca]-=2;
        }
    }
    v[x] = 2;
}

void dfs(int x,int fa) {
    for(auto y:G[x]) {
        if(y==fa) continue;
        dfs(y,x);
        dp[x] += dp[y];
    }
    if(x!=1 && dp[x]==0) ans += m;
    else if(dp[x]==1) ans++;
}

int main() {
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int a,b,i=1;i<n;i++) {
        cin>>a>>b;
        fa[i] = i;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    fa[n] = n;
    for(int a,b,i=0;i<m;i++) {
        cin>>a>>b;
        q[a].push_back(b);
        q[b].push_back(a);
    } 
    tarjan(1);
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}

C++ 解法, 执行用时: 224ms, 内存消耗: 10000K, 提交时间: 2022-02-11 11:21:12

#include<bits/stdc++.h>
using namespace std;
int n,m,h[100001],e[200001],ne[200001],tot,p[100001],mk[100001],d[100001],ans,a,b;
vector<int> qr[100001];
void add(int a,int b){e[++tot]=b;ne[tot]=h[a];h[a]=tot;}
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
void tj(int x){
    mk[x]=1;
    for(int i=h[x];i;i=ne[i]){int y=e[i];if(mk[y])continue;tj(y);p[y]=x;}
    mk[x]=2;
    for(int y:qr[x])if(mk[y]==2)d[x]++,d[y]++,d[find(y)]-=2;
}
int dfs(int x,int fa){
    int res=d[x];
    for(int i=h[x];i;i=ne[i]){
        int y=e[i];
        if(y==fa)continue;
        int s=dfs(y,x);
        if(!s)ans+=m;
        else if(s==1)ans++;
        res+=s;
    }
    return res;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n-1;i++)cin>>a>>b,add(a,b),add(b,a);
	for(int i=1;i<=n;i++)p[i]=i;
    for(int i=0;i<m;i++)cin>>a>>b,qr[a].push_back(b),qr[b].push_back(a);
    tj(1);
    dfs(1,-1);
    cout<<ans;
	return 0; 
}