lessons/参考实现/12-历年真题/洛谷-P9167.cpp

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

using int64 = std::int64_t;

namespace {
constexpr int MOD = 998244353;

int original_vertices;
int difference_limit;
int total_nodes;
int timer_value;
std::vector<std::vector<std::pair<int, int>>> graph;
std::vector<std::vector<int>> block_cut_tree;
std::vector<int> discovery;
std::vector<int> low;
std::vector<int> vertex_stack;

void build_block_cut_tree(int vertex, int parent_edge) {
    discovery[vertex] = low[vertex] = ++timer_value;
    vertex_stack.push_back(vertex);
    for (auto [next, edge_id] : graph[vertex]) {
        if (!discovery[next]) {
            build_block_cut_tree(next, edge_id);
            low[vertex] = std::min(low[vertex], low[next]);
            if (low[next] >= discovery[vertex]) {
                ++total_nodes;
                while (true) {
                    int current = vertex_stack.back();
                    vertex_stack.pop_back();
                    block_cut_tree[total_nodes].push_back(current);
                    block_cut_tree[current].push_back(total_nodes);
                    if (current == next) break;
                }
                block_cut_tree[total_nodes].push_back(vertex);
                block_cut_tree[vertex].push_back(total_nodes);
            }
        } else if (edge_id != parent_edge) {
            low[vertex] = std::min(low[vertex], discovery[next]);
        }
    }
}

std::vector<int> subtree_size;
std::vector<int> maximum_part;
int centroid = 0;

void find_original_centroid(int vertex, int parent) {
    subtree_size[vertex] = vertex <= original_vertices ? 1 : 0;
    maximum_part[vertex] = 0;
    for (int next : block_cut_tree[vertex]) {
        if (next == parent) continue;
        find_original_centroid(next, vertex);
        subtree_size[vertex] += subtree_size[next];
        maximum_part[vertex] = std::max(maximum_part[vertex], subtree_size[next]);
    }
    maximum_part[vertex] =
        std::max(maximum_part[vertex], original_vertices - subtree_size[vertex]);
    if (vertex <= original_vertices &&
        (centroid == 0 || maximum_part[vertex] < maximum_part[centroid]))
        centroid = vertex;
}

std::vector<int> order;
std::vector<std::vector<int>> rooted_children;

void root_tree(int vertex, int parent) {
    order.push_back(vertex);
    subtree_size[vertex] = vertex <= original_vertices ? 1 : 0;
    for (int next : block_cut_tree[vertex]) {
        if (next == parent) continue;
        rooted_children[vertex].push_back(next);
        root_tree(next, vertex);
        subtree_size[vertex] += subtree_size[next];
    }
}

std::vector<int> ways;

void calculate_sizes_zero(int component_size) {
    for (auto iterator = order.rbegin(); iterator != order.rend(); ++iterator) {
        int vertex = *iterator;
        if (subtree_size[vertex] < component_size) continue;
        if (vertex <= original_vertices) {
            int accumulated = 1;
            bool exists = true;
            for (int child : rooted_children[vertex]) {
                if (subtree_size[child] < component_size)
                    accumulated += subtree_size[child];
                else if (ways[child] == 0)
                    exists = false;
            }
            ways[vertex] = accumulated == component_size && exists;
        } else {
            ways[vertex] = 1;
            for (int child : rooted_children[vertex]) {
                if (subtree_size[child] < component_size || ways[child] == 0) {
                    ways[vertex] = 0;
                    break;
                }
            }
        }
        if (subtree_size[vertex] > component_size + 1 && ways[vertex] == 0) {
            ways[centroid] = 0;
            break;
        }
    }
}

void calculate_sizes_one(int component_size) {
    for (auto iterator = order.rbegin(); iterator != order.rend(); ++iterator) {
        int vertex = *iterator;
        if (subtree_size[vertex] < component_size) continue;
        if (vertex <= original_vertices) {
            int accumulated = 1;
            int product = 1;
            int one_large_choice = 0;
            for (int child : rooted_children[vertex]) {
                if (subtree_size[child] < component_size) {
                    accumulated += subtree_size[child];
                } else if (subtree_size[child] == component_size) {
                    if (ways[child] != 0)
                        ++one_large_choice;
                    else
                        accumulated += component_size;
                } else {
                    product = static_cast<int>(static_cast<int64>(product) *
                                               ways[child] % MOD);
                }
            }
            ways[vertex] = 0;
            if (component_size <= accumulated && accumulated <= component_size + 1)
                ways[vertex] = product;
            if (accumulated == 1)
                ways[vertex] = static_cast<int>((ways[vertex] +
                    static_cast<int64>(product) * one_large_choice) % MOD);
        } else {
            ways[vertex] = 1;
            for (int child : rooted_children[vertex]) {
                if (subtree_size[child] < component_size) {
                    ways[vertex] = 0;
                    break;
                }
                ways[vertex] = static_cast<int>(static_cast<int64>(ways[vertex]) *
                                                ways[child] % MOD);
            }
        }
        if (subtree_size[vertex] > component_size + 1 && ways[vertex] == 0) {
            ways[centroid] = 0;
            break;
        }
    }
}

int solve_exact_or_adjacent(int component_size, int limit) {
    std::fill(ways.begin(), ways.end(), 0);
    if (limit == 0) {
        if (original_vertices % component_size != 0) return 0;
        calculate_sizes_zero(component_size);
        return ways[centroid];
    }
    calculate_sizes_one(component_size);
    int adjacent = ways[centroid];
    if (original_vertices % (component_size + 1) == 0) {
        std::fill(ways.begin(), ways.end(), 0);
        calculate_sizes_zero(component_size + 1);
        adjacent -= ways[centroid];
        if (adjacent < 0) adjacent += MOD;
    }
    return adjacent;
}
}  // namespace

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int edge_count;
    std::cin >> original_vertices >> edge_count >> difference_limit;
    int capacity = original_vertices + edge_count + 5;
    graph.assign(original_vertices + 1, {});
    block_cut_tree.assign(capacity, {});
    discovery.assign(original_vertices + 1, 0);
    low.assign(original_vertices + 1, 0);
    for (int id = 0; id < edge_count; ++id) {
        int u, v;
        std::cin >> u >> v;
        graph[u].push_back({v, id});
        graph[v].push_back({u, id});
    }

    total_nodes = original_vertices;
    build_block_cut_tree(1, -1);
    subtree_size.assign(total_nodes + 1, 0);
    maximum_part.assign(total_nodes + 1, 0);
    find_original_centroid(1, 0);

    rooted_children.assign(total_nodes + 1, {});
    order.reserve(total_nodes);
    root_tree(centroid, 0);
    ways.assign(total_nodes + 1, 0);

    std::vector<bool> candidate(original_vertices / 2 + 1, false);
    for (int parts = 2; parts <= original_vertices; ++parts) {
        int small = original_vertices / parts;
        if (small <= original_vertices / 2) candidate[small] = true;
        if (original_vertices % parts == 0 && small > 0)
            candidate[small - 1] = true;
    }

    int answer = 0;
    for (int size = 1; size <= original_vertices / 2; ++size) {
        if (!candidate[size]) continue;
        answer += solve_exact_or_adjacent(size, difference_limit);
        if (answer >= MOD) answer -= MOD;
    }
    std::cout << answer << '\n';
    return 0;
}