結果

問題 No.3346 Tree to DAG
コンテスト
ユーザー areik
提出日時 2025-11-13 23:31:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 964 ms / 2,000 ms
コード長 3,699 bytes
コンパイル時間 5,107 ms
コンパイル使用メモリ 280,000 KB
実行使用メモリ 51,384 KB
最終ジャッジ日時 2025-11-13 23:32:07
合計ジャッジ時間 21,898 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

using isize = size_t;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = long double;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
  _main();
}

i64 pow(i64 x, i64 n) {
  i64 res = 1;
  i64 t = x;
  while (n > 0) {
    if (n & 1) {
      res = res * t;
    }
    t = t * t;
    n >>= 1;
  }
  return res;
}
i64 pow(i64 x, i64 n, i64 m) {
  i64 res = 1;
  i64 t = x % m;
  while (n > 0) {
    if (n & 1) {
      res = res * t % m;
    }
    t = t * t % m;
    n >>= 1;
  }
  return res;
}

vector<i64> g[100000];
vector<p2> dp[100000];
void merge(vector<p2> &dp, p2 v) {
  dp.push_back(v);
  sort(dp.begin(), dp.end());
  reverse(dp.begin(), dp.end());
  set<i64> st;
  vector<p2> ndp;
  for (auto [x, i] : dp) {
    if (st.count(i)) continue;
    ndp.push_back({x, i});
    st.insert(i);
  }
  while (ndp.size() > 3) ndp.pop_back();
  dp = ndp;
}
void dfs(i64 v, i64 par) {
  for (i64 nv : g[v]) {
    if (nv == par) continue;
    dfs(nv, v);
    if (!dp[nv].empty()) merge(dp[v], {dp[nv][0].first + 1, nv});
  }
}
void dfs1(i64 v, i64 par, i64 np) {
  if (np >= 0) merge(dp[v], {np, par});
  for (i64 nv : g[v]) {
    if (nv == par) continue;
    i64 mx = -1;
    for (auto [x, i] : dp[v]) if (i != nv) mx = max(mx, x + 1);
    dfs1(nv, v, mx);
  }
}
void _main() {
  i64 n;
  cin >> n;
  for (i64 i = 0; i < n - 1; i++) {
    i64 u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (i64 i = 0; i < n; i++) {
    for (i64 j = -3; j <= -1; j++) {
      merge(dp[i], {0, j});
    }
  }
  dfs(0, -1);
  dfs1(0, -1, -1);
  vector<set<p2>> v;
  auto add = [](set<p2> &st, i64 x) {
    while (st.count({x, x + 1})) {
      st.erase({x, x + 1});
      x++;
    }
    st.insert({x, x + 1});
  };
  auto del = [](set<p2> &st, i64 x) {
    auto it = st.lower_bound((p2){x + 1, 0});
    if (it == st.begin() || prev(it)->second <= x) {
      if (it == st.end()) {
        st.clear();
        st.insert({1e10, 1e11});
        return;
      }
      auto [l, r] = *it;
      st.erase({l, r});
      st.insert({x, x + 1});
      if (x + 1 < l) st.insert({x + 1, l});
      if (l + 1 < r) st.insert({l + 1, r});
    } else {
      auto [l, r] = *prev(it);
      st.erase({l, r});
      if (l < x) st.insert({l, x});
      if (x + 1 < r) st.insert({x + 1, r});
    }
  };
  vector<i64> ord(n);
  vector<set<p2>> stv(n);
  for (i64 i = 0; i < n; i++) {
    ord[i] = i;
    i64 a = dp[i][0].first;
    i64 b = dp[i][1].first;
    i64 c = dp[i][2].first;
    i64 d = n - 1 - a - b - c;
    set<p2> st;
    add(st, a + d + 2), add(st, b + d + 2), add(st, c + d + 2);
    del(st, d + 1), del(st, d + 2);
    stv[i] = st;
  }
  sort(ord.begin(), ord.end(), [&](i64 a, i64 b){
    set<p2> x = stv[a], y = stv[b];
    while (!x.empty() && !y.empty()) {
      auto [l, r] = *prev(x.end());
      auto [ll, rr] = *prev(y.end());
      if (r != rr) {
        return r < rr;
      }
      x.erase({l, r}), y.erase({ll, rr});
      i64 p = max(l, ll);
      if (l < p) x.insert({l, p});
      if (ll < p) y.insert({ll, p});
    }
    if (x.empty() && y.empty()) return a < b;
    if (x.empty()) return true;
    return false;
  });
  mint ans = 0;
  set<p2> st = stv[ord[0]];
  for (auto [a, b] : st) {
    for (i64 i = a; i < b; i++) {
      ans += mint(2).pow(i);
    }
  }
  ans = mint(2).pow(n + 2) - ans;
  cout << ans.val() << "\n";
}
0