点分治 TLE on#10 求调,AC 变猫娘
查看原帖
点分治 TLE on#10 求调,AC 变猫娘
925044
Xia_Qian楼主2025/7/19 09:00
#include <bits/extc++.h>

int main() {
    // freopen(R"(C:\Users\Administrator\CLionProjects\Test\test.in)", "r", stdin);
    int n, m;
    std::cin >> n >> m;
    // std::cout << n << " " << m << std::endl;
    struct Edge {
        int to, next, len;
    };
    std::vector<Edge> edge;
    std::vector h(n + 1, -1);
    auto addEdge = [&](int x, int y, int len) {
        edge.push_back({y, h.at(x), len});
        h.at(x) = static_cast<int>(edge.size()) - 1;
    };
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    std::vector<int> vis(n + 1);
    std::vector<int> size(n + 1);
    std::vector<int> weight(n + 1);
    auto get_rt = [&](int r, int f, int sum) {
        int res = r;
        weight.at(r) = sum;
        auto get_rt = [&](auto &&dfs, int u, int fa) -> void {
            size.at(u) = 1;
            if (u != r) {
                weight.at(u) = 0;
            }
            for (int i = h.at(u); i != -1; i = edge.at(i).next) {
                int to = edge.at(i).to;
                if (to == fa || vis.at(to)) {
                    continue;
                }
                dfs(dfs, to, u);
                size.at(u) += size.at(to);
                weight.at(u) = std::max(weight.at(u), size.at(to));
            }
            weight.at(u) = std::max(weight.at(u), sum - size.at(u));
            if (weight.at(u) < weight.at(res)) {
                res = u;
            }
        };
        get_rt(get_rt, r, f);
        return res;
    };
    std::vector<int> ask(m + 1);
    for (int i = 1; i <= m; ++i) {
        std::cin >> ask.at(i);
    }
    std::vector cnt(n + 1, std::vector(n / 2 + 1, 0));
    std::vector<int> d(1);
    std::vector<int> dis(n + 1);
    std::vector<int> t(10000001);
    std::vector<int> ans(m + 1);
    auto get_dis = [&](int u, int fa) {
        auto get_dis = [&](auto &&get_dis, int u, int fa) -> void {
            d.push_back(dis.at(u));
            for (int i = h.at(u); i != -1; i = edge.at(i).next) {
                int to = edge.at(i).to;
                if (to == fa || vis.at(to)) {
                    continue;
                }
                int len = edge.at(i).len;
                dis.at(to) = dis.at(u) + len;
                get_dis(get_dis, to, u);
            }
        };
        get_dis(get_dis, u, fa);
    };
    auto dfs = [&](int r) {
        auto dfs = [&](auto &&dfs, int u, int fa) -> void {
            vis.at(u) = 1;
            std::vector<int> vec;
            t.at(0) = 1;
            for (int i = h.at(u); i != -1; i = edge.at(i).next) {
                int to = edge.at(i).to;
                if (to == fa || vis.at(to)) {
                    continue;
                }
                int len = edge.at(i).len;
                dis.at(to) = len;
                d.resize(1);
                get_dis(to, u);
                for (int j = 1; j < d.size(); ++j) {
                    for (int k = 1; k <= m; ++k) {
                        if (ask.at(k) < d.at(j)) {
                            continue;
                        }
                        ans.at(k) |= t.at(ask.at(k) - d.at(j));
                    }
                }
                for (int j = 1; j < d.size(); ++j) {
                    if (d.at(j) > 10000000) {
                        continue;
                    }
                    if (!t.at(d.at(j))) {
                        t.at(d.at(j)) = 1;
                        vec.push_back(d.at(j));
                    }
                }
            }
            for (auto &&item: vec) {
                t.at(item) = 0;
            }
            // std::cout << u << " from " << fa << std::endl;
            for (int i = h.at(u); i != -1; i = edge.at(i).next) {
                int to = edge.at(i).to;
                // std::cout << "    to " << to << std::endl;
                if (to == fa || vis.at(to)) {
                    continue;
                }
                int rt = get_rt(to, u, size.at(u));
                dfs(dfs, rt, rt);
            }
        };
        dfs(dfs, r, r);
    };
    int rt = get_rt(1, 1, n);
    dfs(rt);
    for (int i = 1; i <= m; ++i) {
        std::cout << (ans.at(i) == 1 ? "AYE" : "NAY") << std::endl;
    }
    return 0;
}
2025/7/19 09:00
加载中...