結果

問題 No.399 動的な領主
ユーザー mayocornmayocorn
提出日時 2023-06-17 13:49:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 520 ms / 2,000 ms
コード長 4,685 bytes
コンパイル時間 4,781 ms
コンパイル使用メモリ 272,744 KB
実行使用メモリ 20,768 KB
最終ジャッジ日時 2023-09-07 10:29:30
合計ジャッジ時間 10,812 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 3 ms
4,380 KB
testcase_05 AC 33 ms
4,728 KB
testcase_06 AC 505 ms
16,412 KB
testcase_07 AC 488 ms
16,564 KB
testcase_08 AC 486 ms
16,480 KB
testcase_09 AC 497 ms
16,560 KB
testcase_10 AC 4 ms
4,380 KB
testcase_11 AC 25 ms
4,688 KB
testcase_12 AC 359 ms
16,952 KB
testcase_13 AC 361 ms
16,684 KB
testcase_14 AC 95 ms
20,768 KB
testcase_15 AC 135 ms
20,640 KB
testcase_16 AC 218 ms
18,528 KB
testcase_17 AC 520 ms
16,412 KB
testcase_18 AC 479 ms
16,548 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// type
typedef long long ll;
typedef long double ld;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template<class T> using v = vector<T>;
#define V vector
#define pl pair<ll, ll>
#define vl v<ll>
#define vp v<pl>
#define vm v<mint>
 
// IN-OUT
#define NYAN ios::sync_with_stdio(false);cin.tie(nullptr);cout<<fixed<<setprecision(15);
void Yes(bool b=1) { cout << ( b == 1 ? "Yes" : "No" ) << "\n"; }
void YES(bool b=1) { cout << ( b == 1 ? "YES" : "NO" ) << "\n"; }
void No(bool b=1) { cout << ( b == 1 ? "No" : "Yes" ) << "\n"; }
void NO(bool b=1) { cout << ( b == 1 ? "NO" : "YES" ) << "\n"; }
void CIN() {}
template <typename T, class... U> void CIN(T &t, U &...u) { cin >> t; CIN(u...); }
void COUT() { cout << "\n"; }
template <typename T, class... U, char sep = ' '> void COUT(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; COUT(u...); }
#define dump(x) cerr << #x << ":"<< x << "\n";
#define vdump(x) rep(repeat, sz(x)) cerr << repeat << ":" << x[repeat] << "\n";
 
// macro
#define bp __builtin_popcountll
#define ALL(x) x.begin(),x.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define reps(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define sz(x) (ll)x.size()
ll xd[]={0, 1, 0, -1, 1, 1, -1, -1};
ll yd[]={1, 0, -1, 0, 1, -1, -1, 1};

// function
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll rmax(ll a, ll b){return max(a, b);}
ll rmin(ll a, ll b){return min(a, b);}
ll rsum(ll a, ll b){return a + b;}
ll rzero(){return 0;}

// constant
long double PI = 3.14159265358979;
#define INF32 2147483647
#define INF64 9223372036854775807
#define INF 922337203685477580
using mint = modint998244353;
// using mint = modint1000000007;


/* SOLVE BEGIN ************************************************************************** */

// hld ------------------------------
template < typename T = int >
struct hld {
  int n, root;
  vector<vector<int>> to;
  vector<int> par, subsz, in, head;
  
  hld(int n) : n(n), to(n), par(n), subsz(n), in(n), head(n) {}
  
  void add_edge(int a, int b) {
    to[a].push_back(b);
    to[b].push_back(a);
  }
  
  void dfs1(int v, int p) {
    par[v] = p;
    subsz[v] = 1;
    if(to[v].size() && to[v][0] == p) swap(to[v][0], to[v].back());
    for(int i = 0; i < (int)to[v].size(); i++) {
      auto u = to[v][i];
      if(u == p) continue;
      dfs1(u, v);
      subsz[v] += subsz[u];
      if(subsz[to[v][0]] < subsz[u]) swap(to[v][0], to[v][i]);
    }
  }
  
  void dfs2(int v, int p, int &t) {
    in[v] = t++;
    for(auto u : to[v]) {
      if(u == p) continue;
      head[u] = (to[v][0] == u ? head[v] : u);
      dfs2(u, v, t);
    }
  }
  
  void init(int _root = 0) {
    root = _root;
    dfs1(root, -1);
    int t = 0;
    dfs2(root, -1, t);
  }
  
  vector<pair<int, int>> get_edge(int u, int v) {
    vector<pair<int, int>> res;
    while(1) {
      if(in[u] > in[v]) swap(u, v);
      if(head[u] == head[v]) break;
      res.emplace_back(in[head[v]], in[v] + 1);
      v = par[head[v]];
    }
    if(in[u] + 1 != in[v] + 1) res.emplace_back(in[u] + 1, in[v] + 1);
    return res;
  }
  
  vector<pair<int, int>> get_vertex(int u, int v) {
    vector<pair<int, int>> res;
    while(1) {
      if(in[u] > in[v]) swap(u, v);
      if(head[u] == head[v]) break;
      res.emplace_back(in[head[v]], in[v] + 1);
      v = par[head[v]];
    }
    res.emplace_back(in[u], in[v] + 1);
    return res;
  }
};
// hld ------------------------------

using S = pair<ll, ll>;
S op(S a, S b){return S{a.first + b.first, a.second + b.second};} //セグ木の関数
S e(){return S{0, 0};} //単位元

using F = int;
S mapping(F a, S b){return S{b.first, b.second + a * b.first};} //モノイドに作用させるやつ
F composition(F a, F b){return {a + b};} //関数合成 bが元の関数 aが新しく合成する関数(注意)
F id(){return 0;} //単位元



void solve()
{
  ll n;
  cin >> n;
  hld t(n);
  
  rep(i, n - 1){
    ll a, b;
    cin >> a >> b;
    a--; b--;
    t.add_edge(a, b);
  }
  
  t.init();
  lazy_segtree<S, op, e, F, mapping, composition, id> sg(n);
  rep(i, n) sg.set(i, S{1, 0});
  
  ll q, ans = 0;
  cin >> q;
  while(q--){
    ll a, b;
    cin >> a >> b;
    a--; b--;
    auto vec = t.get_vertex(a, b);
    for(auto [l, r] : vec){
      sg.apply(l, r, 1);
      ans += sg.prod(l, r).second;
    }
  }
  
  cout << ans << "\n";
}

int main()
{
  NYAN
  solve();
  return 0;
}
0