QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#800743#9655. Divide a Treeucup-team004Compile Error//C++236.4kb2024-12-06 15:13:592024-12-06 15:13:59

Judging History

你现在查看的是最新测评结果

  • [2024-12-06 15:13:59]
  • 评测
  • [2024-12-06 15:13:59]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};
struct HLD {
    int n;
    std::vector<int> siz, top, dep, parent, in, out, seq;
    std::vector<std::vector<int>> adj;
    int cur;
    
    HLD() {}
    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 0;
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(int root = 0) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (parent[u] != -1) {
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));
        }
        
        siz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                std::swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
    
    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    
    int jump(int u, int k) {
        if (dep[u] < k) {
            return -1;
        }
        
        int d = dep[u] - k;
        
        while (dep[top[u]] > d) {
            u = parent[top[u]];
        }
        
        return seq[in[u] - dep[u] + d];
    }
    
    bool isAncester(int u, int v) {
        return in[u] <= in[v] && in[v] < out[u];
    }
    
    int rootedParent(int u, int v) {
        std::swap(u, v);
        if (u == v) {
            return u;
        }
        if (!isAncester(u, v)) {
            return parent[u];
        }
        auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
            return in[x] < in[y];
        }) - 1;
        return *it;
    }
    
    int rootedSize(int u, int v) {
        if (u == v) {
            return n;
        }
        if (!isAncester(v, u)) {
            return siz[v];
        }
        return n - siz[rootedParent(u, v)];
    }
    
    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};

void solve() {
    int N;
    std::cin >> N;
    
    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
        a[i]--;
    }
    
    HLD t(N);
    for (int i = 1; i < N; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        t.addEdge(u, v);
    }
    t.work();
    
    std::vector<std::vector<int>> vec(N);
    for (int i = 0; i < N; i++) {
        vec[a[i]].push_back(i);
    }
    
    std::vector<int> dp(N);
    
    std::vector<std::vector<std::vector<std::array<int, 2>>>> comp(N);
    
    for (int c = 0; c < N; c++) {
        if (vec[c].empty()) {
            continue;
        }
        auto &a = vec[c];
        std::sort(a.begin(), a.end(),
            [&](int x, int y) {
                return t.in[x] < t.in[y];
            });
        int m = a.size();
        for (int i = 1; i < m; i++) {
            a.push_back(t.lca(a[i - 1], a[i]));
        }
        std::sort(a.begin(), a.end(),
            [&](int x, int y) {
                return t.in[x] < t.in[y];
            });
        a.erase(std::unique(a.begin(), a.end()), a.end());
        
        std::vector<std::array<int, 2>> edges;
        std::vector<int> stk;
        for (auto x : a) {
            if (stk.empty()) {
                stk.push_back(x);
            } else {
                while (!t.isAncester(stk.back(), x)) {
                    stk.pop_back();
                }
                edges.push_back({stk.back(), x});
            }
        }
        
        comp[a[0]].push_back(std::move(edges));
    }
    
    std::vector<int> g(N);
    
    Fenwick<int> fen(N);
    auto dfs = [&](this auto &&self, int x) -> void {
        for (auto y : t.adj[x]) {
            self(y);
            g[x] += dp[y];
        }
        dp[x] = g[x];
        
        for (const auto &e : comp[x]) {
            int res = 1 + g[x];
            for (auto [u, v] : e) {
                res += fen.sum(t.in[v] + 1);
                res -= fen.sum(t.in[u] + 1);
            }
            dp[x] = std::max(dp[x], res);
        }
        fen.add(t.in[x], g[x] - dp[x]);
        if (t.out[x] < N) {
            fen.add(t.out[x], -g[x] + dp[x]);
        }
    };
    dfs(0);
    
    std::cout << dp[0] << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    for (int i = 1; i <= t; i++) {
        std::cout << "Case " << i << ": ";
        solve();
    }
    
    return 0;
}

詳細信息

answer.code: In function ‘void solve()’:
answer.code:238:20: error: expected identifier before ‘this’
  238 |     auto dfs = [&](this auto &&self, int x) -> void {
      |                    ^~~~
answer.code:238:20: error: expected ‘,’ or ‘...’ before ‘this’
answer.code: In lambda function:
answer.code:239:29: error: ‘x’ was not declared in this scope
  239 |         for (auto y : t.adj[x]) {
      |                             ^
answer.code:240:13: error: ‘self’ was not declared in this scope
  240 |             self(y);
      |             ^~~~
answer.code:243:12: error: ‘x’ was not declared in this scope
  243 |         dp[x] = g[x];
      |            ^