結果
問題 | No.2531 Coloring Vertices on Namori |
ユーザー |
|
提出日時 | 2023-11-03 23:32:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 931 bytes |
コンパイル時間 | 841 ms |
コンパイル使用メモリ | 84,940 KB |
最終ジャッジ日時 | 2025-02-17 18:57:47 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <iostream>#include <vector>#include <atcoder/dsu>#include <atcoder/modint>using mint = atcoder::modint998244353;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, k;std::cin >> n >> k;std::vector<std::vector<int>> g(n);atcoder::dsu uf(n);int x = -1, y = -1;for (int i = 0; i < n; ++i) {int u, v;std::cin >> u >> v;--u, --v;if (uf.same(u, v)) {x = u, y = v;} else {g[u].push_back(v);g[v].push_back(u);uf.merge(u, v);}}std::vector<int> d(n);auto dfs = [&](auto dfs, int u, int p) -> void { for (int v : g[u]) if (v != p) d[v] = d[u] + 1, dfs(dfs, v, u); };dfs(dfs, x, -1);int t = d[y] + 1;mint a = mint(k - 1).pow(n), b = mint(k - 1).pow(n - t + 1);std::cout << (t % 2 ? a - b : a + b).val() << std::endl;}