#1101664 (C++23) No.3193 Submit Your Solution

提出ソース
結果

問題	No.3193 Submit Your Solution
ユーザー	zoidzium (zz)
提出日時	2025-06-27 22:50:08
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	TLE
実行時間	-
コード長	21,426 bytes
コンパイル時間	5,105 ms
コンパイル使用メモリ	322,436 KB
実行使用メモリ	107,052 KB
最終ジャッジ日時	2025-06-27 22:50:31
合計ジャッジ時間	16,707 ms
ジャッジサーバーID （参考情報）	judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	TLE * 1 -- * 16
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vl = vector<ll>;
using vul = vector<ull>;
using vs = vector<string>;
using vvs = vector<vs>;
using vd = vector<double>;
using vvl = vector<vl>;
using vvd = vector<vd>;
using xy = pair<ll, ll>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;
using vvvl = vector<vvl>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define cnt(i, n, m) for (ll i = (n); i <= (m); i++)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define square(a) ((a) * (a))
#define bfind(a, b) (((a) >> (b)) & 1ll)
#define bset(a, b, c) (((c) != 0) ? (a) | (1ll << (b)) : ~((~(a)) | (1 << (b))))
#define nth(a, b) (((a) >> (b)) & 1)

namespace zz_zout {

void ZOUT(const ll Hier, const ll PlaneHier, const string sep) {};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const Elm elm) {
  cout << elm << sep;
  if (Hier >= PlaneHier) cout << endl;
};

void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const char elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const string elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const ll elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const ull elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const int elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, const uint elm) {
  cout << elm << sep;
};

void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const float elm) {
  cout << elm << sep;
};
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const double elm) {
  cout << elm << sep;
};

template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const pair<Elm1, Elm2> pr) {
  cout << "<" << sep;
  ZOUT(Hier + 1, PlaneHier, sep, pr.first);
  ZOUT(Hier + 1, PlaneHier, sep, pr.second);
  cout << ">" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const vector<Elm> vec) {
  cout << "[" << sep;
  each(ite, vec) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const list<Elm> vec) {
  cout << "[" << sep;
  each(ite, vec) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const set<Elm> set) {
  cout << "[" << sep;
  each(ite, set) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const multiset<Elm> set) {
  cout << "[" << sep;
  each(ite, set) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const unordered_set<Elm> set) {
  cout << "[" << sep;
  each(ite, set) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const unordered_multiset<Elm> set) {
  cout << "[" << sep;
  each(ite, set) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const map<Elm1, Elm2> map) {
  cout << "[" << sep;
  each(ite, map) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const multimap<Elm1, Elm2> map) {
  cout << "[" << sep;
  each(ite, map) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const unordered_map<Elm1, Elm2> map) {
  cout << "[" << sep;
  each(ite, map) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm1, class Elm2>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const unordered_multimap<Elm1, Elm2> map) {
  cout << "[" << sep;
  each(ite, map) ZOUT(Hier + 1, PlaneHier, sep, *ite);
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const stack<Elm> csta) {
  stack<Elm> sta = csta;
  cout << "(" << sep;
  while (!sta.empty()) {
    ZOUT(Hier + 1, PlaneHier, sep, sta.top());
    sta.pop();
  }
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const queue<Elm> cque) {
  queue<Elm> que = cque;
  cout << "(" << sep;
  while (!que.empty()) {
    ZOUT(Hier + 1, PlaneHier, sep, que.front());
    que.pop();
  }
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const priority_queue<Elm> cque) {
  priority_queue<Elm> que = cque;
  cout << "(" << sep;
  while (!que.empty()) {
    ZOUT(Hier + 1, PlaneHier, sep, que.top());
    que.pop();
  }
  cout << "]" << sep;
  if (Hier >= PlaneHier) cout << endl;
};
template <class Elm>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep,
          const deque<Elm> cque) {
  deque<Elm> que = cque;
  cout << "(" << sep;
  while (!que.empty()) {
    ZOUT(Hier + 1, PlaneHier, sep, que.front());
    que.pop_front();
  }
  cout << ")" << sep;
  if (Hier >= PlaneHier) cout << endl;
};

template <class Head, class... Tail>
void ZOUT(const ll Hier, const ll PlaneHier, const string sep, Head&& head,
          Tail&&... tails) {
  // zout(head);
  cout << head << sep;
  ZOUT(Hier + 1, PlaneHier, sep, forward<Tail>(tails)...);
  if (Hier >= PlaneHier) cout << endl;
};

////////////////////////////////////////
template <ll Hier = 10>
void zout() {
  cout << endl;
};

template <ll PlaneHier = 10, ll Sep = 1, class... Args>
void zout(Args&&... args) {
  ZOUT(1, PlaneHier, string(max<ll>(0, Sep), ' '), forward<Args>(args)...);
  cout << endl;
};

};  // namespace zz_zout
using namespace zz_zout;

namespace zz_time {
std::chrono::_V2::system_clock::time_point START_TIME =
    std::chrono::system_clock::now();

ll currentTime(std::chrono::_V2::system_clock::time_point st = START_TIME) {
  std::chrono::_V2::system_clock::time_point now =
      std::chrono::system_clock::now();
  return (ll)(std::chrono::duration_cast<std::chrono::milliseconds>(now - st)
                  .count());
};
};  // namespace zz_time
using namespace zz_time;

namespace zz_random {
std::random_device RANDOM_DEVICE;
std::mt19937 RANDOM_MT;
void setSeed(const ll& seed = RANDOM_DEVICE()) {
  RANDOM_MT = std::mt19937(seed);
};

std::uniform_int_distribution<int> createIntDistribution(const ll& L = 0,
                                                         const ll& R = 1) {
  return std::uniform_int_distribution<int>(L, R);
};
std::uniform_real_distribution<double> createDoubleDistribution(
    const double& L = 0.0, const double& R = 1.0) {
  return std::uniform_real_distribution<double>(L, R);
};
std::normal_distribution<double> createNormalDistribution(
    const double& average = 0.0, const double& standard_deviation = 1.0) {
  return std::normal_distribution<double>(average, standard_deviation);
}
bool getProbability(const double& p = 0.5) {
  return (createDoubleDistribution()(RANDOM_MT) <= 0.5);
}
};  // namespace zz_random
using namespace zz_random;

namespace zz_modulo {
class pp {
 public:
  ll e = 0;
  ll mod = 2;
  ll inv = 0;

  pp& operator=(const pp& x);
  pp operator+();
  pp operator-();
  template <typename T>
  pp& operator+=(const T& y);
  template <typename T>
  pp& operator-=(const T& y);
  template <typename T>
  pp& operator*=(const T& y);
  template <typename T>
  pp& operator/=(T& y);
  ll exp(ll x, ll I, ll modulo);
  pp exp(pp& x, ll I);
  pp exp(ll I);
  void cal_inv();
  pp inversion();
  string str() const;

  pp(const ll& elm = 0, const ll& modulo = 998244353, const ll& inversion = 0) {
    mod = modulo;
    e = elm;
    if (e < 0) {
      e = mod - ((-e) % mod);
    } else {
      e %= mod;
    }
    mod = modulo;
    if (inversion < 0) {
      cal_inv();
    } else if (inversion != 0) {
      inv = inversion;
    }
  };

  static vector<pp> create_vp(ll N, const ll& modulo);
  static pp chineseRemainderTheorem(vector<pp> vx);
  static pp garner(vector<pp> vx, const ll& mod);
};

pp& pp::operator=(const pp& x) {
  this->e = x.e;
  this->mod = x.mod;
  this->inv = x.inv;
  return *this;
};
pp operator+(const pp& x, const pp& y) {
  ll elm = x.e + y.e;
  if (elm > x.mod) elm -= x.mod;
  return pp(elm, x.mod);
};
template <typename T>
pp operator+(const pp& x, const T& y) {
  pp z(y, x.mod);
  return (x + z);
};
template <typename T>
pp operator+(const T& x, const pp& y) {
  pp z(x, y.mod);
  return (z + y);
};
template <typename T>
pp& pp::operator+=(const T& y) {
  *this = (*this) + y;
  return *this;
};

pp pp::operator+() { return *this; };

pp operator-(const pp& x, const pp& y) {
  ll elm = x.e - y.e;
  if (elm < 0) elm += x.mod;
  return pp(elm, x.mod);
};
template <typename T>
pp operator-(const pp& x, const T& y) {
  pp z(y, x.mod);
  return (x - z);
};
template <typename T>
pp operator-(const T& x, const pp& y) {
  pp z(x, y.mod);
  return (z - y);
};
template <typename T>
pp& pp::operator-=(const T& y) {
  *this = (*this) - y;
  return *this;
};

pp pp::operator-() { return (0 - (*this)); };

pp operator*(const pp& x, const pp& y) {
  return pp((x.e * y.e) % x.mod, x.mod, (x.inv * y.inv) % x.mod);
};
template <typename T>
pp operator*(const pp& x, const T& y) {
  pp z(y, x.mod);
  return (x * z);
};
template <typename T>
pp operator*(const T& x, const pp& y) {
  pp z(x, y.mod);
  return (z * x);
};
template <typename T>
pp& pp::operator*=(const T& y) {
  *this = (*this) * y;
  return *this;
};

pp operator/(const pp& x, pp& y) { return (x * y.inversion()); }
template <typename T>
pp operator/(const pp& x, T& y) {
  pp z(y, x.mod);
  return (x / z);
};
template <typename T>
pp operator/(const T& x, pp& y) {
  pp z(x, y.mod);
  return (z / y);
};
template <typename T>
pp& pp::operator/=(T& y) {
  *this = (*this) / y;
  return *this;
};

bool operator==(const pp& x, const pp& y) { return (x.e == y.e); }
template <typename T>
bool operator==(const T& x, const pp& y) {
  return (x == y.e);
};
template <typename T>
bool operator==(const pp& x, const T& y) {
  return (x.e == y);
};

bool operator!=(const pp& x, const pp& y) { return !(x == y); }
template <typename T>
bool operator!=(const T& x, const pp& y) {
  return !(x == y);
};
template <typename T>
bool operator!=(const pp& x, const T& y) {
  return !(x == y);
};

ll pp::exp(ll x, ll I, ll modulo) {
  ll y = 1;
  if (x < 0) {
    x = (modulo - ((-x) % modulo));
  } else {
    x %= modulo;
  }
  while (I > 0) {
    if (I & 1) {
      y = (y * x) % modulo;
    }
    x = (x * x) % modulo;
    I /= 2;
  };
  return y;
};

pp pp::exp(pp& x, ll I) {
  x.cal_inv();
  pp xx = x;
  pp y(1, xx.mod, 1);
  while (I > 0) {
    if (I & 1) {
      y = (y * xx);
    }
    xx = (xx * xx);
    I /= 2;
  };
  return y;
}

pp pp::exp(ll I) { return exp(*this, I); }

void pp::cal_inv() {
  if (this->inv <= 0) this->inv = exp(this->e, this->mod - 2, this->mod);
};

pp pp::inversion() {
  cal_inv();
  return pp(this->inv, this->mod, this->e);
}

string pp::str() const {
  return ("<epi " + to_string(e) + " \t" + to_string(mod) + " \t" +
          to_string(inv) + " >");
}

using vp = vector<zz_modulo::pp>;

vector<pp> pp::create_vp(ll N, const ll& modulo) {
  // m=m%i+m/i * i
  // 0- (m % i) = (m/i)*i
  cout << "!!" << endl;
  N = max<ll>(1, N);
  vector<pp> vec(N + 1);
  vec[0].e = 0;
  vec[0].mod = modulo;
  vec[0].inv = 1;
  vec[1].e = 1;
  vec[1].mod = modulo;
  vec[1].inv = 1;
  cnt(i, 2, N) {
    vec[i] = pp(i, modulo);
    cout << "@[" << i << "]=" << vec[i].str() << endl;
    cout << "---" << vec[modulo / i].str() << flush;
    cout << "  " << vec[modulo % i].str() << endl;
    vec[i].inv = (0 - ((modulo / i) * vec[modulo % i].inversion())).e;
    cout << " [" << i << "]=" << vec[i].str() << endl;
  }
  return vec;
};

pp chineseRemainderTheorem(vector<pp>& vx) {
  ll m = 1;
  each(ite, vx) m *= ite->mod;
  pp ans(0, m);
  each(ite, vx) {
    // ll Ai = R[i];
    // ll Mi = MMM / MM[i];
    // ll Ni = pp(Mi, MM[i]).inversion().e;

    // ANS += Ai * Mi * Ni;

    ll Ai = ite->e;
    ll Mi = m / ite->mod;
    ll Ni = pp(Mi, ite->mod, -1).inv;
    ans += pp(Ai * Mi * Ni, m);
    // zout(ans.str(), ite->str(), m, Ai, Mi, Ni);
  }

  return ans;
};

pp garner(vector<pp>& vx, const ll& mod) {
  ll N = vx.size();
  vector<vector<pp>> R(N, vector<pp>(N));
  rep(i, N) {
    cnt(j, i, N - 1) {
      if (i == j) {
        R[i][i] = vx[i].inversion();
      } else {
        R[i][j] = pp(vx[i].e, vx[j].mod, -1).inversion();
      }
      // zout("#ij=", i, j);
    }
  }
  vector<pp> X(N);
  rep(i, N) {
    X[i] = vx[i];
    rep(j, i) {
      // zout("ij=", i, j);
      X[i] = (X[i] - X[j].e) * R[j][i];
    }
    // cout << "x[" << i << "]=" << X[i].str() << endl;
  }
  // rep(i, N) zout(X[i].str());
  pp ANS(0, mod), P(1, mod);
  rep(i, N) {
    ANS += P.e * X[i].e;
    P *= vx[i].mod;
  }
  return ANS;
};

};  // namespace zz_modulo
using namespace zz_modulo;

namespace zz_prime {
class prime {
 public:
  static vl sieve;
  static vl p;
  static void set(ll N = 1000000) {
    N = max<ll>(2, N) + 1;
    sieve = vl(N, 0);
    p.clear();
    sieve[0] = 1;
    sieve[1] = 1;
    cnt(i, 2, N - 1) {
      if (sieve[i] == 0) {
        p.push_back(i);
        ll j = i;
        while (j < N) {
          if (sieve[j] == 0) sieve[j] = i;
          j += i;
        }
      }
    }
  };

  static bool isprime(ll x) {
    if (x <= 1) return false;
    if (sieve.empty()) set();
    if (x < sieve.size()) return (sieve[x] == x);
    each(ite, p) {
      if (x < (*ite) * (*ite)) return true;
      if ((x % (*ite)) == 0) return false;
    }
    return true;
  };

  static vxy factor(ll x) {
    x = max<ll>(1, x);
    if (sieve.empty()) set();

    map<ll, ll> MAP;
    each(ite, p) {
      if (x < sieve.size()) break;

      while ((x % (*ite)) == 0) {
        MAP[*ite]++;
        x /= *ite;
      }
    }

    if (x < sieve.size()) {
      while (x > 1) {
        MAP[sieve[x]]++;
        x /= sieve[x];
      }
    } else {
      MAP[x]++;
    }
    vxy fact;
    each(ite, MAP) fact.push_back(*ite);
    return fact;
  };

  static vl divisors(const vxy& fact) {
    vl ans(1, 1);
    function<void(const ll&, const ll&)> Func =
        [&fact, &ans, &Func](const ll& I, const ll& Elm) -> void {
      if (fact.empty()) return;
      ll Add = 1;

      if ((I + 1) < fact.size()) {
        Func(I + 1, Elm);
      } else {
        if (Elm != 1) ans.emplace_back(Elm);
      }

      cnt(i, 1, fact[I].second) {
        Add *= fact[I].first;
        if ((I + 1) < fact.size()) {
          Func(I + 1, Elm * Add);
        } else {
          ans.emplace_back(Elm * Add);
        }
      };
    };
    Func(0, 1);
    sort(ans.begin(), ans.end());
    return ans;
  };
};

vl prime::p;
vl prime::sieve;
}  // namespace zz_prime
using namespace zz_prime;

/////////////////////////////////////////////////
namespace lca {
void set(const ll& N, const ll R, const vvl& E, vl& D, vvl& Q) {
  D = vl(N, -2);
  Q = vvl(N);
  queue<pair<xy, ll>> QUE;
  QUE.emplace(make_pair(R, R), 0);
  D[R] = -1;
  ll AT, PAR, Deep;
  while (!QUE.empty()) {
    AT = QUE.front().first.first;
    D[AT] = QUE.front().second;
    Deep = 0;
    while ((1LL << Deep) <= D[AT]) Deep++;
    Q[AT] = vl(max<ll>(1, Deep));
    Q[AT][0] = QUE.front().first.second;
    cnt(i, 1, Deep - 1) Q[AT][i] = Q[Q[AT][i - 1]][i - 1];
    QUE.pop();
    each(ite, E[AT]) {
      if (D[*ite] == -2) {
        D[*ite] = -1;
        QUE.emplace(make_pair(*ite, AT), D[AT] + 1);
      }
    }
  }
};

ll ancestor(const vl& D, const vvl& Q, const ll& U, const ll& N) {
  if (N == 0) return U;
  for (ll i = Q[U].size() - 1; i >= 0; i--) {
    if ((1LL << i) <= N) return ancestor(D, Q, Q[U][i], N - (1LL << i));
  }
  return U;
};

ll find(const vl& D, const vvl& Q, ll U, ll V) {
  if (D[U] > D[V]) swap(U, V);
  V = ancestor(D, Q, V, D[V] - D[U]);
  while (U != V) {
    ll L = 0, R = Q[U].size(), C;
    while ((L + 1) < R) {
      C = (L + R) / 2;
      if (Q[U][C] == Q[V][C]) {
        R = C;
      } else {
        L = C;
      }
    }
    U = Q[U][L];
    V = Q[V][L];
  }
  return U;
};

void preOrder(const ll& N, const ll R, const vvl& E, vl& PO) {
  PO = vl(N, -1);
  ll PreI = 0;
  function<void(ll)> Func = [&Func, &PreI, &E, &PO](const ll& AT) {
    PO[AT] = PreI;
    PreI++;
    each(ite, E[AT]) if (PO[*ite] == -1) Func(*ite);
  };
  Func(R);
};

ll subTree(const vl& D, const vvl& Q, const vl& PO, vl& Vs, vl& P) {
  if (Vs.empty()) return -1;

  map<ll, ll> Par;
  each(ite, Vs) Par[*ite] = -1;
  sort(Vs.begin(), Vs.end(),
       [&PO](const ll& A, const ll& B) { return (PO[A] < PO[B]); });
  ll K = Vs.size();
  Vs.push_back(Vs[0]);
  stack<ll> STA;
  STA.push(Vs[0]);
  cnt(I, 1, K) {
    // cout << "Par[" << Vs[I] << "]=";
    // each(ite, Par) cout << "<" << ite->first << " " << ite->second << ">";
    // cout << endl;

    ll V = STA.top();
    ll W = lca::find(D, Q, V, Vs[I]);
    if (Par.find(W) == Par.end()) Par[W] = -1;
    // cout << "-- V=" << V << " W=" << W << "  |STA|=" << STA.size() << endl;
    ll PreV = V;
    while (D[V] >= D[W]) {
      STA.pop();

      if (STA.empty()) {
        Par[V] = W;
        PreV = V;
        V = -1;
        break;
      } else {
        Par[V] = STA.top();
        PreV = V;
        V = STA.top();
      }
    }
    Par[PreV] = W;

    if (!STA.empty()) Par[W] = V;
    STA.push(W);
    PreV = V;
    V = W;
    if (I == K) break;
    Par[Vs[I]] = V;
    STA.push(Vs[I]);
    PreV = V;
    V = Vs[I];
  }
  Vs.pop_back();

  Vs = vl();
  P = vl();
  each(ite, Par) {
    Vs.push_back(ite->first);
    P.push_back(ite->second);
  }
  return Vs.size();
}

};  // namespace lca

/////////////////////////////////////////////////

int main() {
  ll N;
  cin >> N;
  vxy UV(N - 1), XY(N - 1);
  rep(i, N - 1) cin >> UV[i].first >> UV[i].second;
  rep(i, N - 1) cin >> XY[i].first >> XY[i].second;

  vvl Ea(N), Qa;
  vl Da;
  vvl Eb(N), Qb;
  vl Db;

  rep(i, N - 1) {
    Ea[UV[i].first - 1].push_back(UV[i].second - 1);
    Ea[UV[i].second - 1].push_back(UV[i].first - 1);

    Eb[XY[i].first - 1].push_back(XY[i].second - 1);
    Eb[XY[i].second - 1].push_back(XY[i].first - 1);
  }

  lca::set(N, 0, Ea, Da, Qa);
  lca::set(N, 0, Eb, Db, Qb);

  // ull Lmt = 1;
  // ull Lmt2 = 1;

  // zout("Lmt=", Lmt, " ", Lmt + 1, " ", Lmt - 1);
  // cnt(i, 1, 64) {
  //   Lmt2 <<= 1ULL;
  //   zout(i, Lmt2);
  // }

  // cnt(i, 1, 63) { Lmt <<= 1ULL; }

  // zout("Lmt=", Lmt, " Lmt2=", Lmt2, " ", Lmt == Lmt2);
  // return 0;

  // vl ANS(64, 0);
  // ull Lmt = (1 << 64) - 2;
  // zout(Lmt);
  // cout << bitset<64>(18446744073709551614) << endl;

  // ll B63all = 18446744073709551614;

  // cout << B63all << endl;
  // return 0;
  // ull ANS = 0;

  /////
  // vl ANS(63, 0);
  ull XXX = 0;

  ll Add, DistA, DistB;
  rep(i, N - 1) cnt(j, i + 1, N-1) {
    DistA = 1;
    DistB = 1;
    ll Pa = lca::find(Da, Qa, i, j);
    ll Pb = lca::find(Db, Qb, i, j);

    if (Pa == i) {
      DistA = abs(Da[i] - Da[j]);
    } else if (Pa == j) {
      DistA = abs(Da[j] - Da[i]);

    } else {
      DistA = abs(Da[Pa] - Da[i]) + abs(Da[Pa] - Da[j]);
    }
    if (Pb == i) {
      DistB = abs(Db[i] - Db[j]);
    } else if (Pb == j) {
      DistB = abs(Db[j] - Db[i]);

    } else {
      DistB = abs(Db[Pb] - Db[i]) + abs(Db[Pb] - Db[j]);
    }
    Add = DistA * DistB;

    XXX += 2 * Add;
    // ll AddAdd = Add;
    // ll AT = 0;
    // ll P = 0;
    // while (((Add > 0) || (P > 0)) && (AT < 63)) {
    //   if (Add & 1) {
    //     P++;
    //   }
    //   ll E = ANS[AT] + P;
    //   P = (E >= 2);
    //   ANS[AT] = (E & 1);

    //   AT++;
    //   Add >>= 1;
    // }
    // zout(DistA, DistB, Add, ANS);
    // ll Res = B63all - Add;
    // if (Res <= ANS) {
    //   ANS += Add - B63all;
    // } else {
    //   ANS += Add;
    // }
    // ANS=(ANS+(( DistA* DistB)%Mod)%Mod;
    ////
    // zout(i, j, DistA, DistB, AddAdd, "\t", ANS);
  }
  cout << XXX << endl;
  // ull Cnt = 0;
  // zout(ANS);
  // rep(i, 63) {
  //   ll I = 62 - i;
  //   Cnt <<= 1;
  //   Cnt += (ANS[I]);
  //   // zout(I, Cnt);
  // }
  // cout << Cnt << endl;
  return 0;
}
yukicoder

結果

ソースコード
