2025-03 · 8级 · 割裂

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 1659 字

CCF 原卷官方标程 · 数组与向量、位运算、搜索、图论 · 本地编译通过

2025-03
数组与向量

正文

// GESP 2025-03 C++ 8级 编程题 2 · 割裂
// 原题：https://oj.yecheng.tv/p/gs2503l8p2
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1669257026863136.pdf
// 题意：小杨有一棵包含个节点的树，其中节点的编号从到 。
// 知识点：数组与向量、位运算、搜索、图论
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：样例验证 1/1 通过
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, k;
vector<int> e[N];
int f[N][25], dep[N], g[N], h[N];
void dfs(int u, int fa){
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for(int i = 1; i <= 20; i++){
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for(auto v: e[u]){
        if(v == fa) continue;
        dfs(v, u);
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    int t = dep[u] - dep[v];
    for(int i = 0; i <= 20; i++){
        if(t & (1 << i)) u = f[u][i];
    }
    for(int i = 20; i >= 0; i--){
        if(f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];
    }
    if(u == v) return u;
    return f[u][0];
}
int ans;
void dfs2(int u, int fa){
    for(auto v: e[u]){
        if(v == fa) continue;
        dfs2(v, u);
        g[u] += g[v];
        h[u] += h[v];
    }
    if(!g[u] && h[u]) {
        ans++;
    }
}
void solve(){
    cin >> n >> k;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= k; i++){
        int u, v;
        cin >> u >> v;
        int lc = lca(u, v);
        g[u]++, g[v]++, g[lc]--, g[f[lc][0]]--;
    }
    int u, v;
    cin >> u >> v;
    int lc = lca(u, v);
    h[u]++, h[v]++, h[lc]--, h[f[lc][0]]--;
    dfs2(1, 0);
    cout << ans << '\n';
}
int main(){
    solve();
}

2025-03 · 8级 · 割裂

正文

GESP 标程 · 考级真题的其它内容