結果

問題 No.3272 Separate Contractions
ユーザー 👑 hos.lyric
提出日時 2025-09-12 22:32:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 305 ms / 3,000 ms
コード長 4,307 bytes
コンパイル時間 1,270 ms
コンパイル使用メモリ 121,628 KB
実行使用メモリ 43,944 KB
最終ジャッジ日時 2025-09-12 23:42:38
合計ジャッジ時間 13,304 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:77:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   77 |       scanf("%d%d", &A[i], &B[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


int N;
vector<int> A, B;

vector<vector<int>> G;
vector<int> pari, dep;
vector<int> dis, fin;
vector<int> us;

void init() {
  G.assign(N, {});
  pari.assign(N, -1);
  dep.assign(N, 0);
  dis.assign(N, -1);
  fin.assign(N, -1);
  us.clear();
}

pair<int, int> dfs(int u, int pi) {
  pari[u] = pi;
  dis[u] = us.size();
  us.push_back(u);
  pair<int, int> ret(0, u);
  for (const int i : G[u]) if (pi != i) {
    const int v = A[i] ^ B[i] ^ u;
    dep[v] = dep[u] + 1;
    auto res = dfs(v, i);
    ++res.first;
    chmax(ret, res);
  }
  fin[u] = us.size();
  return ret;
}

int main() {
  for (; ~scanf("%d", &N); ) {
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    
    init();
    for (int i = 0; i < N - 1; ++i) {
      G[A[i]].push_back(i);
      G[B[i]].push_back(i);
    }
    const auto res0 = dfs(0, -1);
    const auto res1 = dfs(res0.second, -1);
    vector<int> U, I;
    for (int u = res1.second; ; ) {
      U.push_back(u);
      const int i = pari[u];
      if (!~i) break;
      I.push_back(i);
      u ^= A[i] ^ B[i];
    }
    const int K = I.size();
//cerr<<"U = "<<U<<endl;
//cerr<<"I = "<<I<<endl;
    
    vector<int> on(N - 1, 0);
    for (int k = 0; k < K; ++k) on[I[k]] = 1;
    init();
    for (int i = 0; i < N - 1; ++i) if (!on[i]) {
      G[A[i]].push_back(i);
      G[B[i]].push_back(i);
    }
    for (int k = 0; k <= K; ++k) {
      dfs(U[k], -1);
    }
//cerr<<"dis = "<<dis<<endl;
//cerr<<"fin = "<<fin<<endl;
//cerr<<"us = "<<us<<endl;
    
    Int base = 0;
    for (int k = 0; k <= K; ++k) {
      for (int j = dis[U[k]]; j < fin[U[k]]; ++j) {
        const int u = us[j];
        base += (max(k, K - k) + dep[u]);
      }
    }
cerr<<"base = "<<base<<endl;
    
    vector<Int> ans(N - 1, base);
    
    // moyori full dep?
    int ks[2] = {0, K};
    for (int k = 0; k <= K; ++k) {
      for (int j = dis[U[k]]; j < fin[U[k]]; ++j) {
        const int u = us[j];
        if (dep[u] == k) chmax(ks[0], k);
        if (dep[u] == K - k) chmin(ks[1], k);
      }
    }
    for (int k = 0; k < K; ++k) {
      const int i = I[k];
      // from left
      if (!(ks[1] <= k)) {
        int l = 0, r = k;
        chmin(r, (K-1)/2);
//cerr<<"i = "<<i<<": from left "<<l<<" "<<r<<"; "<<(fin[U[r]] - dis[U[l]])<<endl;
        ans[i] -= (fin[U[r]] - dis[U[l]]);
      }
      // from right
      if (!(k + 1 <= ks[0])) {
        int l = k + 1, r = K;
        chmax(l, K - (K-1)/2);
//cerr<<"i = "<<i<<": from right "<<l<<" "<<r<<"; "<<(fin[U[r]] - dis[U[l]])<<endl;
        ans[i] -= (fin[U[r]] - dis[U[l]]);
      }
      // merged
      ans[i] -= max(k, (K - 1) - k);
    }
    for (int k = 0; k <= K; ++k) {
      for (int j = dis[U[k]] + 1; j < fin[U[k]]; ++j) {
        const int u = us[j];
        const int i = pari[u];
        ans[i] -= (fin[u] - dis[u]);
        ans[i] -= (max(k, K - k) + dep[u] - 1);
      }
    }
    
    for (int i = 0; i < N - 1; ++i) {
      printf("%lld\n", ans[i]);
    }
  }
  return 0;
}
0