P8844 题解

· · 题解

前言

这里给两个完全不需要高级数据结构的做法。一个 O(m \log n)，一个 O(n+m)。

题解

第一种做法

来自班上同学。

由于是染 \ge x 的深度的所有点，所以只需要统计深度 = x 的点的子树大小和就可以了。

但是这样每个点是 O(nm) 的，显然不能过，菊花图即可卡爆。但是过了，且比我的 O(n+m) 还跑得快。申请加强数据。

容易发现一点是：把树看成一层一层的，然后发现一个点的子树内同一高度的点都在类似一段里。然后可以通过对深搜序二分出左端点和右端点。显然可以做前缀和。

在线算法，时间复杂度 O(m \log n)。

代码放一个他的暴力。

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e5 + 10;
int n, m, Dep;
int Size[N];
vector<int> g[N], td[N];
int ins[N], tot;
int dep[N];
void DFS(int now, int fa) {
    dep[now] = dep[fa] + 1;
    td[dep[now]].push_back(now);
    Size[now] = 1;
    ins[now] = ++tot;
    for (int to : g[now])
        if (to != fa)
            DFS(to, now), Size[now] += Size[to];
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    DFS(1, 0);
    for (int i = 1; i <= m; ++i) {
        int op, x;
        cin >> op >> x;
        if (op == 1)
            Dep = x;
        else {
            if (Dep == 0) {
                cout << 0 << "\n";
                continue;
            }
            if (Dep <= dep[x])
                cout << Size[x] << "\n";
            else {
                int ans = 0;
                for (int j : td[Dep])
                    if (ins[j] < ins[x] + Size[x] && ins[x] <= ins[j])
                        ans += Size[j];
                cout << ans << "\n";
            }
        }
    }
    return 0;
}

第二种做法

来自我。完全不用数据结构。

铺垫是借鉴第一种做法的开初思路，即“只统计 = x 的点的子树大小和”。

把询问挂到树上，记录询问编号和 x。

可以想一下从根开始 dfs，当到这个点的询问，就记一下当前要求的 x 这一位上的数是什么，子树所有点都遍历完后再看一下这个值，所以就得到了最终子树内的答案。

对于“这个值”，是之前遍历过的所有点中深度为当前下标的子树大小和。具体见下面代码。

离线算法，O(n+m)。

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
vector<int> g[N];
vector<pair<int, int>> query[N];
int a1[N], b1[N];
int ans1[N], ans2[N], d[N], siz[N], sm[N], n, m;
void init(int u, int fa) {
    d[u] = d[fa] + 1;
    ++siz[u];
    for (int &v : g[u]) {
        if (v == fa)
            continue;
        init(v, u);
        siz[u] += siz[v];
    }
}
void dfs(int u, int fa) {
    for (auto &q : query[u]) {
        ans1[q.second] = sm[q.first];
    }
    sm[d[u]] += siz[u];
    for (int &v : g[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
    }
    for (auto &q : query[u]) {
        if (d[u] >= q.first)
            ans2[q.second] = ans1[q.second] + siz[u];
        else
            ans2[q.second] = sm[q.first];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].emplace_back(v), g[v].emplace_back(u);
    }
    int w = n + 1, tot = 0;
    for (int i = 1, op, x; i <= m; ++i) {
        cin >> op >> x;
        if (op == 1)
            w = x;
        else
            a1[tot] = x, b1[tot] = w, query[x].emplace_back(w, ++tot);
    }
    init(1, 0);
    dfs(1, 0);
    for (int i = 1; i <= tot; ++i) {
        cout << ans2[i] - ans1[i] << "\n";
    }
    cout.flush();
    return 0;
}