题解：P11108 [ROI 2023] 蜗牛与富士山 (Day 2)

· · 题解

About 本题

容易注意到，一个叶节点能否在不超过 k 次转弯内从根到达，只取决于从根到该叶子的路径上的转弯次数，与查询节点 u 无关。因此只需统计 u 子树内合法的叶子数量即可，记为 cnt_u。于是可以预先 DFS 处理 \forall u \in [1,n] 的 cnt_u，询问时输出 cnt_u 即可。时间复杂度 O(n+q)。

代码

#include<bits/stdc++.h>
#define LoveFurina ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F(x, l, r) for(int x = l; x <= r; ++x)
#define B(x, r, l) for(int x = r; x >= l; --x)
#define ll long long
using namespace std;

const int N = 2e5 + 10;

int n, k, q;
struct Node {
    int s[2]; // 0：左节点 1：右节点（方便处理是否同向）
} a[N];
int cnt[N];

inline int dfs(int u, int last, int tot) {
    if (!a[u].s[0]) return cnt[u] = tot <= k;
    int res = 0;
    F (i, 0, 1) {
        int &v = a[u].s[i];
        res += dfs(v, i, tot + (u != 1 && i != last ? 1 : 0)); // 需注意从根节点出发走左右节点均不算作转向
    }
    return cnt[u] = res;
}

int main() {
    LoveFurina;

    cin >> n >> k >> q;
    F (i, 1, n) {
        int t; cin >> t;
        if (t) cin >> a[i].s[0] >> a[i].s[1];
    }

    dfs(1, 0, 0);
    while (q--) {
        int u; cin >> u;
        cout << cnt[u] << '\n';
    }

return 0;
}

About 拓展 \tiny \text{（非进阶型可不看）}