#1169268 (C++23) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: aPNJ777
• 提出日時: 2026-06-18 14:22:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 656 ms / 2,000 ms
• コード長: 15,312 bytes
• コンパイル時間: 5,022 ms
• コンパイル使用メモリ: 361,660 KB
• 実行使用メモリ: 29,900 KB
• 最終ジャッジ日時: 2026-06-18 14:22:20
• 合計ジャッジ時間: 12,317 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
other	AC * 19

ソースコード

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

using ll = long long;
using ld = long double;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;

#define vv(type, name, h, w) vector<vector<type>> name(h, vector<type>(w))
#define vvv(type, name, h, w, l) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(l)))
#define vvvv(type, name, a, b, c, d) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(d))))
#define vvvvv(type, name, a, b, c, d, e) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(e)))))

#define elif else if

#define FOR1(a) for (long long _ = 0; _ < (long long)(a); _++)
#define FOR2(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR3(i, l, r) for (long long i = l; i < (long long)(r); i++)
#define FOR4(i, l, r, c) for (long long i = l; i < (long long)(r); i += c)
#define FOR1_R(a) for (long long _ = (long long)(a) - 1; _ >= 0; _--)
#define FOR2_R(i, n) for (long long i = (long long)(n) - 1; i >= (long long)(0); i--)
#define FOR3_R(i, l, r) for (long long i = (long long)(r) - 1; i >= (long long)(l); i--)
#define FOR4_R(i, l, r, c) for (long long i = (long long)(r) - 1; i >= (long long)(l); i -= (c))
#define overload4(a, b, c, d, e, ...) e
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_in(a, A) for (auto a: A)
#define FOR_each(a, A) for (auto &&a: A)
#define FOR_subset(t, s) for(long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))

#define all(x) x.begin(), x.end()
#define len(x) int(x.size())

int popcount(int x) { return __builtin_popcount(x); }
int popcount(uint32_t x) { return __builtin_popcount(x); }
int popcount(long long x) { return __builtin_popcountll(x); }
int popcount(uint64_t x) { return __builtin_popcountll(x); }
// __builtin_clz(x)は最上位bitからいくつ0があるか.
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(uint32_t x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(uint64_t x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }

// 入力
void rd() {}
void rd(char &c) { cin >> c; }
void rd(string &s) { cin >> s; }
void rd(int &x) { cin >> x; }
void rd(uint32_t &x) { cin >> x; }
void rd(long long &x) { cin >> x; }
void rd(uint64_t &x) { cin >> x; }
template<class T>
void rd(vector<T> &v) {
  for (auto& x:v) rd(x);
}

void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
  rd(h), read(t...);
}

#define CHAR(...) \
  char __VA_ARGS__; \
  read(__VA_ARGS__)

#define STRING(...) \
  string __VA_ARGS__; \
  read(__VA_ARGS__)

#define INT(...) \
  int __VA_ARGS__; \
  read(__VA_ARGS__)

#define U32(...) \
  uint32_t __VA_ARGS__; \
  read(__VA_ARGS__)

#define LL(...) \
  long long __VA_ARGS__; \
  read(__VA_ARGS__)

#define U64(...) \
  uint64_t __VA_ARGS__; \
  read(__VA_ARGS__)

#define VC(t, a, n) \
  vector<t> a(n); \
  read(a)

#define VVC(t, a, h, w) \
  vector<vector<t>> a(h, vector<t>(w)); \
  read(a)

//出力
void wt() {}
void wt(const char c) { cout << c; }
void wt(const string s) { cout << s; }
void wt(int x) { cout << x; }
void wt(uint32_t x) { cout << x; }
void wt(long long x) { cout << x; }
void wt(uint64_t x) { cout << x; }
void wt(double x) { cout << fixed << setprecision(16) << x; }
void wt(long double x) { cout << fixed << setprecision(16) << x; }

template<class T>
void wt(const vector<T> v) {
  int n = v.size();
  for (int i = 0; i < n; i++) {
    if (i) wt(' ');
    wt(v[i]);
  }
}

void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  wt(head);
  if (sizeof...(Tail)) wt(' ');
  print(forward<Tail>(tail)...);
}

/////////////////////////////////////////////////////////////////////////////////////////
template <class T>
int bisect_left(const vector<T> &A, T x) {
  auto idx = lower_bound(A.begin(), A.end(), x) - A.begin();
  return idx;
}

template <class T>
int bisect_right(const vector<T> &A, T x) {
  auto idx = upper_bound(A.begin(), A.end(), x) - A.begin();
  return idx;
}

long long min(long long a, long long b) { return a < b ? a : b; }

template <class T>
T min(vector<T> A) {
  assert (A.size());
  T S = A[0];
  for (T a : A) S = min(a, S);
  return S;
}

template <class T>
T max(vector<T> A) {
  assert (A.size());
  T S = A[0];
  for (T a : A) S = max(a, S);
  return S;
}

template <class T>
T add(T x, T y) { return x + y; }

template <class T>
bool chmin(T & x, T a) { return a < x ? (x = a, true) : false; }

template <class T>
bool chmax(T & x, T a) { return a > x ? (x = a, true) : false; }

template <class T>
T sum(vector<T> A) {
  T S = 0;
  for (int i = 0; i < int(A.size()); i++) S += A[i];
  return S;
}

uint64_t random_u64(uint64_t l, uint64_t r) {
  static std::random_device rd;
  static std::mt19937_64 gen(rd());
  std::uniform_int_distribution<uint64_t> dist(l, r);
  return dist(gen);
}

long long gcd(long long a, long long b) {
  while (a) {
    b %= a;
    if (b == 0) return a;
    a %= b;
  }
  return b;
}

long long lcm(long long a, long long b) {
  if (a * b == 0) return 0;
  return a * b / gcd(a, b);
}

long long pow_mod(long long a, long long r, long long mod) {
  long long res = 1, p = a % mod;
  while (r) {
    if ((r % 2) == 1) res = res * p % mod;
    p = p * p % mod, r >>= 1;
  }
  return res;
}

long long mod_inv(long long a, long long mod) {
  if (mod == 1) return 0;
  a %= mod;
  long long b = mod, s = 1, t = 0;
  while (1) {
    if (a == 1) return s;
    t -= (b / a) * s;
    b %= a;
    if (b == 1) return t + mod;
    s -= (a / b) * t;
    a %= b;
  }
}

long long Garner(vector<long long> Rem, vector<long long> Mod, int MOD) {
  assert (Rem.size() == Mod.size());
  long long mod = MOD;
  Rem.push_back(0);
  Mod.push_back(mod);
  long long n = Mod.size();
  vector<long long> coffs(n, 1);
  vector<long long> constants(n, 0);
  for (int i = 0; i < n - 1; i++) {
    long long v = (Mod[i] + Rem[i] - constants[i]) % Mod[i];
    v *= mod_inv(coffs[i], Mod[i]);
    v %= Mod[i];
    for (int j = i + 1; j < n; j++) {
      constants[j] = (constants[j] + coffs[j] * v) % Mod[j];
      coffs[j] = (coffs[j] * Mod[i]) % Mod[j];
    }
  }
  return constants[n - 1];
}

long long Tonelli_Shanks(long long a, long long mod) {
  a %= mod;
  if (a < 2) return a;
  if (pow_mod(a, (mod - 1) / 2, mod) != 1) return -1;
  if (mod % 4 == 3) return pow_mod(a, (mod + 1) / 4, mod);

  long long b = 3;
  if (mod != 998244353) {
    while (pow_mod(b, (mod - 1) / 2, mod) == 1) {
      b = random_u64(2, mod - 1);
    }
  }

  long long q = mod - 1;
  long long Q = 0;
  while (q % 2 == 0) {
    Q++, q /= 2;
  }

  long long x = pow_mod(a, (q + 1) / 2, mod);
  b = pow_mod(b, q, mod);

  long long shift = 2;
  while ((x * x) % mod != a) {
    long long error = (((pow_mod(a, mod - 2, mod) * x) % mod) * x) % mod;
    if (pow_mod(error, 1 << (Q - shift), mod) != 1) {
      x = (x * b) % mod;
    }
    b = (b * b) % mod;
    shift++;
  }
  return x;
}

long long floor_div(long long a, long long b) {
  if (b < 0) a *= -1, b *= -1;
  if (a >= 0) return a / b;
  return -((-a + b - 1) / b);
}

long long ceil_div(long long a, long long b) {
    if (b < 0) a *= -1, b *= -1;
    if (a >= 0) return (a + b - 1) / b;
    return - ((-a) / b);
}

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

/*
検索するとき

https://www.google.com/search?udm=14&q=

-ai
*/

template <typename T, typename F>
struct lazysegtree {
  int size = 1, n, log = 0;
  T (*op)(T, T);
  T e;
  T (*mapping)(F, T);
  F (*composing)(F, F);
  F id;
  vector<T> data;
  vector<F> lazy;

  lazysegtree(int n, T (*op)(T, T), T e, T (*mapping)(F, T), F (*composing)(F, F), F id) : n(n), op(op), e(e), mapping(mapping), composing(composing), id(id) {
    while (size < n) {
      log++;
      size <<= 1;
    }
    data.resize(2 * size, e), lazy.resize(2 * size, id);
  }

  void set_array(vector<T> A) {
    assert (size >= int(A.size()));
    for (int i = 0; i < int(A.size()); i++) data[size + i] = A[i];
    for (int i = size - 1; i > 0; i--) update(i);
  }

  // 作用後の更新用の関数
  void update(int k) { data[k] = op(data[k << 1], data[(k << 1) + 1]); }

  // 作用用の関数
  void all_apply(int k, F f) {
    data[k] = mapping(f, data[k]);
    if (k < size) lazy[k] = composing(f, lazy[k]);
  }

  // 遅延伝播用の関数
  void push(int k) {
    all_apply(k << 1, lazy[k]), all_apply((k << 1) + 1, lazy[k]);
    lazy[k] = id;
  }

  void set(int i, T x) {
    assert (0 <= i && i < n);
    i += size;
    for (int h = log; h > 0; h--) push(i >> h);
    data[i] = x;
    for (int h = 1; h < log + 1; h++) update(i >> h);
  }

  T get(int i) {
    assert (0 <= i && i < size);
    i += size;
    for (int h = log; h > 0; h--) push(i >> h);
    return data[i];
  }

  // 区間積の取得
  T prod(int l, int r) {
    assert (0 <= l && l <= r && r <= n);
    if (l == r) return e;
    // 根からO(logN)個の区間のnodeにlazyを伝播しながら行く.
    l += size, r += size;
    for (int i = log; i > 0; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push(r >> i);
    }
    // 区間積の取得
    T L = e, R = e;
    while (l < r) {
      if (l & 1) L = op(L, data[l]), l += 1;
      if (r & 1) R = op(data[r -= 1], R);
      l >>= 1, r >>= 1;
    }
    return op(L, R);
  }

  // 1点作用
  void apply_point(int i, F f) {
    assert (0 <= i && i < size);
    i += size;
    for (int h = log; h > 0; h--) push(i >> h);
    data[i] = mapping(f, data[i]);
    for (int h = 1; h < log + 1; h++) update(i >> h);
  }
  
  // 区間作用
  void apply(int l, int r, F f) {
    assert (0 <= l && l <= r && r <= size);
    if (l == r) return;
    // 根からO(logN)個の区間のnodeにlazyを伝播しながら行く.
    l += size, r += size;
    for (int i = log; i > 0; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    // O(logN)個の区間のnodeに作用, その子に伝播.
    int ll = l, rr = r;
    while (l < r) {
      if ((l & 1) == 1) all_apply(l, f), l++;
      if ((r & 1) == 1) all_apply(r -= 1, f);
      l >>= 1, r >>= 1;
    }
    // 根に向かってdataの更新
    l = ll, r = rr;
    for (int i = 1; i < log + 1; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
    return;
  }
  
  // 二分探索
  int max_right(int l, function<bool(T)> check) {
    assert (0 <= l && l <= n);
    assert (check(e));
    if (l == n) return n;
    l += size;
    for (int i = log; i > 0; i--) push(l >> i);
    T sm = e;
    while (1) {
      while (l % 2 == 0) l >>= 1;
      if (!check(op(sm, data[l]))) {
        while (l < size) {
          push(l), l <<= 1;
          if (check(op(sm, data[l]))) sm = op(sm, data[l]), l += 1;
        }
        return l - size;
      }
      sm = op(sm, data[l]), l += 1;
      if ((l & -l) == l) break;
    }
    return n;
  }

  int min_left(int r, function<bool(T)> check) {
    assert (0 <= r && r <= n);
    assert (check(e));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i > 0; i--) push((r - 1) >> i);
    T sm = e;
    while (1) {
      r -= 1;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!check(op(data[r], sm))) {
        while (r < size) {
          push(r), r = 2 * r + 1;
          if (check(op(data[r], sm))) sm = op(data[r], sm), r -= 1;
        }
        return r + 1 - size;
      }
      sm = op(data[r], sm);
      if ((r & -r) == r) break;
    }
    return 0;
  }

};

struct Heavy_Light_Decomposition {
  int N, root, idx = 0;
  vector<vector<int>> G;
  vector<int> sub, depth, order, tout, head, parent;
  Heavy_Light_Decomposition(vector<vector<int>> & G, int root)
  : N(int(G.size())), root(root), G(G), sub(N, 0), depth(N, 0),
  order(N, -1), tout(N, -1), head(N, root), parent(N, -1) { dfs_size(root), dfs_HLD(root); }

  void dfs_size(int u) {
    sub[u] = 1;
    for (auto & v : G[u]) {
      if (v == parent[u]) {
        if (G[u].size() >= 2 && v == G[u][0]) swap(G[u][0], G[u][1]);
        else continue;
      }
      depth[v] = depth[u] + 1;
      parent[v] = u;
      dfs_size(v);
      sub[u] += sub[v];
      if (sub[v] > sub[G[u][0]]) swap(G[u][0], v);
    }
  }

  void dfs_HLD(int u) {
    order[u] = idx;
    idx++;
    for (auto v : G[u]) {
      if (v == parent[u]) continue;
      head[v] = (G[u][0] == v ? head[u] : v);
      dfs_HLD(v);
    }
    tout[u] = idx;
  }

  int LCA(int u, int v) {
    while (head[u] != head[v]) {
      if (order[u] > order[v]) swap(u, v);
      v = parent[head[v]];
    }
    if (depth[u] < depth[v]) return u;
    else return v;
  }

  int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[LCA(u, v)]; }

  // ascend, descend 両方とも u -> v のパスの通り掛け順を計算
  vector<pair<int, int>> ascend(int u, int v) {
    if (u == v) return {};
    vector<pair<int, int>> res;
    while (head[u] != head[v]) {
      res.push_back({order[u], order[head[u]]});
      u = parent[head[u]];
    }
    if (u != v) res.push_back({order[u], order[v] + 1});
    return res;
  }

  vector<pair<int, int>> descend(int u, int v) {
    if (u == v) return {};
    vector<pair<int, int>> res;
    while (head[u] != head[v]) {
      res.push_back({order[head[v]], order[v]});
      v = parent[head[v]];
    }
    if (u != v) res.push_back({order[u] + 1, order[v]});
    reverse(all(res));
    return res;
  }

  template<typename F>
  void path_query(int u, int v, F & f, bool vertex = 0) {
    int lca = LCA(u, v);
    for (auto [a, b] : ascend(u, lca)) f(a + 1, b);
    if (vertex) f(order[lca], order[lca] + 1);
    for (auto [a, b] : descend(lca, v)) f(a, b + 1);
  }

  template<typename F>
  void subtree_query(int u, F & f, bool vertex = 0) { f(order[u] + int(!vertex), tout[u]); } 

};

struct mono { long long x, c; };

mono op(mono x, mono y) { return {x.x + y.x, x.c + y.c}; }

mono e = {0, 0};

mono mapping(long long f, mono x) { return {x.x + f * x.c, x.c}; }

void solve() {
  INT(N);
  vector<vector<int>> G(N);
  FOR(N - 1) {
    INT(u, v);
    u--, v--;
    G[u].push_back(v), G[v].push_back(u);
  }
  Heavy_Light_Decomposition HLD(G, 0);
  lazysegtree<mono, long long> seg(N, op, e, mapping, add, 0);
  for (int i = 0; i < N; i++) seg.set(i, {1, 1});
  long long ans = 0;
  auto f = [&](int l, int r) {
    ans += seg.prod(min(l, r), max(l, r)).x;
    seg.apply(min(l, r), max(l, r), 1);
    return;
  };
  INT(Q);
  FOR(Q) {
    INT(u, v);
    u--, v--;
    HLD.path_query(u, v, f, 1);
  }
  print(ans);
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int testcases = 1;
  //cin >> testcases;
  FOR(testcases) solve();
}