暗的连锁

C++(g++ 7.5.0) 解法, 执行用时: 156ms, 内存消耗: 15412K, 提交时间: 2022-08-26 21:37:14

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

const int N = 100010;
int fa[N][22], dep[N], d[N];
vector<int> adj[N];
int n, m;

void dfs1(int u, int f) {
    dep[u] = dep[f] + 1;
    
    fa[u][0] = f;
    for (int i = 1; i <= 21; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }

    for (int v : adj[u]) {
        if(v == f) {
            continue;
        }
        dfs1(v, u);
    }
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for (int i = 21; i >= 0; i--) {
        if(dep[fa[a][i]] >= dep[b]) {
            a = fa[a][i];
        }
    }

    if(a == b) return a;

    for (int i = 21; i >= 0; i--) {
        if(fa[a][i] != fa[b][i]) {
            a = fa[a][i];
            b = fa[b][i];
        }
    }

    return fa[a][0];
}

int ans = 0;
void dfs2(int u, int f) {
    for (int v : adj[u]) {
        if(v == f) {
            continue;
        }
        dfs2(v, u);
        if(d[v] == 0) ans += m;
        else if(d[v] == 1) ans++;
        d[u] += d[v];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs1(1, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        d[u]++, d[v]++;
        int p = lca(u, v);
        d[p] -= 2;
    }

    dfs2(1, 0);

    cout << ans << "\n";

    return 0;
}

C++14(g++5.4) 解法, 执行用时: 387ms, 内存消耗: 18036K, 提交时间: 2020-01-21 10:56:49

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

const int MAXN = 1e5+1;
int N, M;
vector<int> G[MAXN];
int F[MAXN][20];
int H[MAXN];
int cnt[MAXN];
int tot = 0;

void dfs_lca(int s, int f) {
  F[s][0] = f, H[s] = H[f]+1;
  for (int i = 0; i < 19; i++) F[s][i+1] = F[F[s][i]][i];
  for (auto t: G[s]) if (t != f) dfs_lca(t, s);
}

int lca(int x, int y) {
  if (H[x] < H[y]) swap(x, y);
  for (int i = 19; i >= 0; i--) if (H[F[x][i]] >= H[y]) x = F[x][i];
  if (x == y) return x;
  for (int i = 19; i >= 0; i--) if (F[x][i] != F[y][i]) x = F[x][i], y = F[y][i];
  return F[x][0];
}
int dfs(int s, int f) {
  int tot = 0;
  for (auto t: G[s]) if (t != f) {
    tot += dfs(t, s);
    cnt[s] += cnt[t];
  }
  if (f == 0) return tot;
  if (cnt[s] == 0) tot += M;
  if (cnt[s] == 1) tot += 1;
  return tot;
}

int main() {
  cin >> N >> M;
  for (int i = 0; i < N-1; i++) {
    int u, v; cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs_lca(1, 0);
  for (int i = 0; i < M; i++) {
    int x, y; cin >> x >> y;
    int z = lca(x, y);
    cnt[x]++, cnt[y]++, cnt[z]-=2;
  }
  cout << dfs(1, 0) << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 427ms, 内存消耗: 18256K, 提交时间: 2020-05-30 21:19:42

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int N,M;
vector<int> G[MAXN];
int F[MAXN][20];
int H[MAXN];
int cnt[MAXN];
int tot=0;
void dfs_lca(int s,int f)
{
	F[s][0]=f,H[s]=H[f]+1;
	for(int i=0;i<19;i++)
	F[s][i+1]=F[F[s][i]][i];
	for(auto t:G[s])
	if(t!=f)
	dfs_lca(t,s);
}
int lca(int x,int y)
{
	if(H[x]<H[y]) swap(x,y);
	for(int i=19;i>=0;i--)
	if(H[F[x][i]]>=H[y]) x=F[x][i];
	if(x==y) 
	return x;
	for(int i=19;i>=0;i--)
	if(F[x][i]!=F[y][i])
	x=F[x][i],y=F[y][i];
	return F[x][0];
}
int dfs(int s,int f)
{
	int tot=0;
	for(auto t:G[s])
	if(t!=f)
	{
		tot+=dfs(t,s);
		cnt[s]+=cnt[t];
	}
	if(f==0) return tot;
	if(cnt[s]==0) tot+=M;
	if(cnt[s]==1) tot+=1;
	return tot;
}
int main()
{
	cin>>N>>M;
	for(int i=0;i<N-1;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs_lca(1,0);
	for(int i=0;i<M;i++)
	{
		int x,y;
		cin>>x>>y;
		int z=lca(x,y);
		cnt[x]++,cnt[y]++,cnt[z]-=2;
	}
	cout<<dfs(1,0)<<endl;
}

详情