結果

問題 No.399 動的な領主
ユーザー Astral__Astral__
提出日時 2023-11-11 15:59:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 969 ms / 2,000 ms
コード長 12,370 bytes
コンパイル時間 3,546 ms
コンパイル使用メモリ 236,132 KB
実行使用メモリ 26,880 KB
最終ジャッジ日時 2023-11-11 16:00:00
合計ジャッジ時間 13,198 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,424 KB
testcase_01 AC 4 ms
7,424 KB
testcase_02 AC 5 ms
7,424 KB
testcase_03 AC 5 ms
7,424 KB
testcase_04 AC 9 ms
7,552 KB
testcase_05 AC 66 ms
8,576 KB
testcase_06 AC 957 ms
17,536 KB
testcase_07 AC 929 ms
17,536 KB
testcase_08 AC 969 ms
17,664 KB
testcase_09 AC 908 ms
17,664 KB
testcase_10 AC 12 ms
7,552 KB
testcase_11 AC 48 ms
8,576 KB
testcase_12 AC 638 ms
18,048 KB
testcase_13 AC 630 ms
18,048 KB
testcase_14 AC 239 ms
26,880 KB
testcase_15 AC 316 ms
26,880 KB
testcase_16 AC 445 ms
22,656 KB
testcase_17 AC 958 ms
17,664 KB
testcase_18 AC 932 ms
17,664 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using PT = priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>>;
using PPQ = priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>;
using PQ = priority_queue<ll, vector<ll>, greater<ll>>;
using P =  pair<ll, ll>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvc = vector<vector<vector<char>>>;
using vvvd = vector<vector<vector<double>>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvs = vector<vector<string>>;
using vvc = vector<vector<char>>;
using vvp = vector<vector<pair<ll, ll>>>;
using vvb = vector<vector<bool>>;
using vvd = vector<vector<double>>;
using vp = vector<pair<ll, ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
#define vvvm = vector<vector<vector<mint>>>
#define vvm = vector<vector<mint>>
#define vm = vector<mint>
#define umap = unordered_map
#define uset = unordered_set
#define rrr(l, r) mt()%(r-l+1)+l
#define rep(i, s, f) for(ll i = s; i <= f; i++)
#define per(i, s, f) for(ll i = s; i >= f; i--)
#define all0(x) (x).begin() ,(x).end()
#define all(x) (x).begin() + 1, (x).end()
#define ENDL '\n'

////////////////////////////////////////////////////////////////////////////////////////////////////////////
//これが本当の組み込み関数ってね（笑）

template <typename T>
T or_less(vector<T> &A, T x) { //x以下で最大要素の添字 前提: sort済み 存在しない: -1
  return distance(A.begin(), upper_bound(A.begin(), A.end(), x)-1);
}
template <typename T>
T under(vector<T> &A, T x) { //x未満の最大要素の添字　前提: sort済み 存在しない: -1
  return distance(A.begin(), lower_bound(A.begin(), A.end(), x)-1);
}
template <typename T>
T or_more(vector<T> &A, T x) { //x以上で最小要素の添字　　前提: sort済み 存在しない: N .   //distanceのA.beginは添字を出すために常にA.begin() NG: A.begin() + 1
  return distance(A.begin(), lower_bound(A.begin(), A.end(), x));
}
template <typename T>
T over(vector<T> &A, T x) { //xより大きい最小要素の添字前提: sort済み 存在しない: N
  return distance(A.begin(), upper_bound(A.begin(), A.end(), x));
}
template <typename T>
vector<T> vec_shift(vector<T> A, ll step, ll dir = 1, ll indexed = 1) {//dir = 1 : 右シフト  dir = -1 : 左シフト
  ll N = A.size() - indexed;
  vector<T> res(N+1);
  rep(i, indexed, N) {
    ll idx = i - step * dir;
    if(idx < indexed) idx += N;
    if(idx > N) idx -= N;
    res.at(i) = A.at(idx);
  }
  return res;
}
template <typename T>
void UNIQUE(vector<T> &A) {
    sort(all0(A));
  return A.erase(unique(A.begin(), A.end()), A.end());
}
template <typename T>
void rev90(vector<vector<T>> &A, int indexed = 1) {
  reverse(A.begin() + indexed, A.end());
  int n = A.size();
  rep(i, indexed, n-1) {
   rep(j, i+1, n-1) {
      swap(A.at(i).at(j), A.at(j).at(i));
    }
  }
}
int msb(long long a) {
    if(a == 0) return -1;
    return 64 - int(__builtin_clzll(a));
}
void chmin(ll &a, ll b) {
  a = min(a, b);
}
void chmax(ll &a, ll b) {
  a = max(a, b);
}
//////////////////////////////////////////////////////////////////////
//数学系
///////////////////////////////////////////////////////////////////////
ll round(ll x, ll i) {return ll(x + 5 * pow(10, i-1))/ll(pow(10, i)) * ll(pow(10, i));}
vp insu_bunkai(ll N) {
  vp res;
  for (ll i = 2; i * i <= N; i++) {
    ll cnt = 0;
    while(N % i == 0) {
      cnt++;
      N /= i;
    }
    if(cnt != 0) res.push_back(P(i, cnt));
  }
  if(N != 1) res.push_back(P(N, 1));
  return res;
}
ll extgcd (ll a, ll b,  ll &x, ll &y) {
  if(b == 0) { x = 1;y = 0;return a;}
  ll d = extgcd(b, a%b, y, x);
  y -= a/b * x;
  return d;
}
template <typename T>
T ceil(T a, T b) {
  assert(b != 0);
  if(a % b == 0) return a / b;
  if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b + 1;
  else return a / b;
}
template <typename T>
T floor(T a, T b) {
  assert(b != 0);
  if(a % b == 0) return a / b;
  if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b;
  else return a/b - 1;
}
ll modpow(ll x, ll y, ll mod) {
  if(x > mod) x %= mod;
  if(y == 0) return 1;
  ll res = modpow(x, y >> 1, mod);
  res = res * res % mod;
  if(y & 1) res *= x, res %= mod;
  return res;
}
ll sqrt_(ll a) {
    ll l = 0;
    ll r = 3037000499LL;
    while(l < r) {
        ll mid = (l + r + 1) / 2;
        if(mid * mid <= a) l = mid;
        else r = mid - 1;
    }
    return l;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//グローバル変数を置くところ（情報工学意識高め）
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
const ll int_max = 1001001001;
const ll ll_max = 1001001001001001001LL;
const double pi = 3.141592653589793;
vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1};  // (番兵) → ↓ ← ↑  ※ 右から時計回り 注 : グリッド or 座標で上下は反転する。
vl dy{0, 0, -1, 0, 1, 1, -1, -1, 1};
//const ll mod = 1000000007;
//const ll mod = 998244353;


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<typename X, typename M>
struct LazySegTree {
  using FX = function<X(X, X)>;//全て右側を左側に作用させる。 : Xを融合させる
  using FA = function<X(X, M)>;//Xに作用素Mを作用させる
  using FM = function<M(M, M)>;//作用素を合成する
  using FL = function<M(M, int)>;//作用素の影響が長さに関係のある場合
  int n;
  FX fx; 
  FA fa;
  FM fm;
  FL fl;
  const X ex;//単位元
  const M em;//単位元
  vector<X> dat;
  vector<M> lazy;
  LazySegTree(int siz, FX _fx, FA _fa, FM _fm, FL _fl, X _ex, M _em) : fx(_fx), fa(_fa), fm(_fm), fl(_fl), ex(_ex), em(_em) {
    n = 1;
    while(n < siz) n <<= 1;
    dat.assign(n * 2, ex);
    lazy.assign(n * 2, em);
  }

  void set(int i, X x) {
    dat.at(i + n - 1) =  x;
  }

  void init() {
    per(i, n-1, 1) {
      dat.at(i) = fx(dat.at(i*2), dat.at(i * 2 + 1));
    }
  }

  void eval(int k, int len) {
    if(lazy[k] == em) return;
    if(k < n) {
      lazy[k * 2] = fm(lazy[k * 2], lazy[k]);
      lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
    }
    dat[k] = fa(dat[k], fl(lazy[k], len));
    lazy[k] = em;
  }

  void update(int a, int b, M m, int l, int r,  int k) {
    eval(k, r-l);
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) {
      lazy[k] = fm(lazy[k], m);
      eval(k, r-l);
    }
    else {
      int mid = (l + r)/2;
      update(a, b, m, l, mid, k * 2);
      update(a, b, m, mid, r, k * 2 + 1);
      dat[k] = fx(dat[k * 2], dat[k * 2 + 1]);
    }
  }

  X query(int a, int b, int l, int r, int k) {
    eval(k,r-l);
    if(r <= a || b <= l) return ex;
    if(a <= l && r <= b) return dat[k];
    ll mid = (l + r)/2;
    X L = query(a, b, l, mid, k * 2);
    X R = query(a, b, mid, r, k * 2 + 1);
    return fx(L, R);
  }

  void change(int l, int r, M m) {
    update(l, r + 1, m, 1, n + 1, 1);
  }
  X get(int l, int r) {
    return query(l, r + 1, 1, n + 1, 1);
  }
};

//int siz, FX _fx, FA _fa, FM _fm, FL _fl, X _ex, M _em

using XX = ll;
XX ex = 0;

using MM = ll;
MM em = 0;

XX fx(const XX& a, const XX& b) {
  return a+b;
}

MM fm(const MM& a, const MM& b) {
  return a+b;
}

XX fa(const XX& a, const MM& b) {
  return a + b;
}

MM fl(const MM& a, const int& l) {
  return a * l;
}

LazySegTree<XX, MM> seg(100000, fx, fa, fm, fl, ex, em);

template <typename X>
struct HL {
  vector<int> siz;//[元の頂点番号] = サイズ
  vector<int> num;//[元の頂点番号] = 振り直した頂点番号
  vector<int> numrev;
  vector<int> par;//[振られた] = 振られた 自分の親
  vector<int> head;//[振られた番号] = 振られた番号 自分の連結成分の頭
  int N;
  vector<X> dat;//セグ木用の配列
  int size = 1;
  

  HL(int _N, vvl& G): N(_N) {
    par.resize(N+1);
    iota(par.begin(), par.end(), 0);
    siz.resize(N+1, 1);
    num.assign(N+1, -1);
    numrev.resize(N+1, -1);
    head.resize(N+1);
    while(size < N) size <<= 1;
    dat.assign(size*2, ex);

    auto dfs_siz = [&](auto dfs_siz, int now, int prev) -> void {
      int sum = 1;
      for(int to : G[now]) {
        if(to == prev) continue;
         dfs_siz(dfs_siz, to, now);
         sum += siz[to];
      }
      siz[now] = sum;
      return;
    };
    dfs_siz(dfs_siz, 1, -1);
    rep(i, 1, N){
      sort(G[i].begin(), G[i].end(), [&](int a, int b) {
        return siz[a] > siz[b];
      });
    }

    int idx = 1;
    auto dfs_bunkai = [&](auto dfs_bunkai, int now, int prev, int hed) -> void {
      num[now] = idx;//番号付
      numrev[idx] = now;
      idx++;
      par[num[now]] = prev;//親の頂点   //1だけは直前も自分も1
      if(hed == -1)hed = num[now];
      head[num[now]] = hed;

      bool flag = true;
      
      rep(i, 0, int(G[now].size()) - 1) {
        if(num[G[now][i]] != -1) continue;
        if(flag) dfs_bunkai(dfs_bunkai, G[now][i], num[now], hed), flag = false;
        else dfs_bunkai(dfs_bunkai, G[now][i], num[now], -1);
      }
      return;
    };
    dfs_bunkai(dfs_bunkai, 1, 1, -1);
  }
  // 振り終わった
  //////////////////////////////////////////

  X get(int u, int v) {// 入 : 元番号
    int w = num[getLCA(u, v)];//lcaで左右に分ける
    u = num[u];
    v = num[v];
    X L = ex, R = ex;
    while(u != w) {
      int hed = max<int>(head[u], w+1);
      seg.change(hed, u, 1);
      L = fx(seg.get(hed, u), L); //交換則を意識してない　意識するならqueryから変えなきゃいけない(あるいは、配列を分けるか？）
      if(hed != w)  u = par[hed];
      else u = w;
    }   
    seg.change(w, w, 1);
    L = fx(seg.get(w, w), L);//根から上の方へ
    while(v != w) {
      int hed = max<int>(head[v], w+1);
      seg.change(hed, v, 1);
      R = fx(seg.get(hed, v), R); //根から上の方へ
      if(hed != w)  v = par[hed];
      else v = w;
    }
    //R = operation(query(1, size+1, w, w+1, 1), R); これをしてないので、RはまだLCAに辿り着いてない。
    return fx(L, R);//交換則を要する時はこの行を変更する必要があるかもしれない : 無いと思うが
  }

  int getLCA(int a, int b) {//入 : 元番号  出 : 元番号
    a = num[a];
    b = num[b];
    while(true) {
      if(a > b) swap(a, b);
      if(head[a] == head[b]) return numrev[a];
      b = par[head[b]];
    }
  }

  int parent(int a) {//入 : 元番号
    return numrev[par[num[a]]];
  }
};


void solve() {
  ll N;
  cin >> N;
  vvl G(N+1);
  rep(i,1,N-1){
    ll u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  ll ans = 0;
  HL<XX> hld(N, G);
  ll Q;
  cin >> Q;

  rep(qi, 1, Q) {
    ll a, b;
    cin >> a >> b;
    ans += hld.get(a, b);
  }

  cout << ans << endl;
 

}
//尺取り法的な事をする時は、rは勿論"lもNを超え無いようにする"事！（違反するとエラーコード139が出たりする)
//無断で0を平方数にカウントする人もいる
//”部分文字列”と”連続部分文字列”は違うので確認すること
//一般のグラフと、有向辺かつその貼り方に制約がある(多くの場合：番号がで解放に伸びる）はだいぶ違うので確認すること
//座標を2で割った時の”切り捨て側(左側）”を求めるには 誤:(x / 2) マイナスの時！！！ 正:floor<ll>(x, 2);
//stringでの数字の下から1桁目は 正:S.at(N-1)  誤:S.at(0)
//if(S.at(i) == 1)　← charなのに1...?
// modは取りましたか...?(´・ω・｀)
//sortの比較関数は、 a == b　ならば falseを返す必要がある（そうで無いとRE(発生しない場合もある））



int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cout << fixed << setprecision(15);
    ll T = 1;
    //cin >> T;
    rep(i, 1, T) {
        solve();
    }
  return 0;
}
0