結果

問題 No.399 動的な領主
ユーザー Kutimoti_TKutimoti_T
提出日時 2018-08-22 11:32:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 558 ms / 2,000 ms
コード長 5,188 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 181,920 KB
実行使用メモリ 16,208 KB
最終ジャッジ日時 2024-06-06 03:49:31
合計ジャッジ時間 8,085 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 35 ms
5,376 KB
testcase_06 AC 541 ms
15,692 KB
testcase_07 AC 530 ms
15,568 KB
testcase_08 AC 532 ms
15,696 KB
testcase_09 AC 532 ms
15,568 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 28 ms
5,376 KB
testcase_12 AC 382 ms
16,124 KB
testcase_13 AC 393 ms
16,208 KB
testcase_14 AC 161 ms
16,204 KB
testcase_15 AC 235 ms
16,204 KB
testcase_16 AC 305 ms
15,824 KB
testcase_17 AC 558 ms
15,544 KB
testcase_18 AC 544 ms
15,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <set>
#include <stack>
#include <queue>
using namespace std;


/* include file*/
#include <functional>
#include <vector>
using namespace std;

template <class Monoid>
struct LazySegment {
  using Func = function<Monoid(Monoid, Monoid)>;
  vector<Monoid> node;
  vector<Monoid> lazy;
  vector<bool> lazyFlag;
  int n;
  Monoid ide;
  Monoid lazy_init;

  Monoid func(Monoid a,Monoid b){
    return a + b;
  }

  Monoid lazy_make(int l,int r,Monoid x,Monoid lazy){
    return lazy + (r - l) * x;
  }

  Monoid lazy_effect(Monoid node,Monoid lazy){
    return node + lazy;
  }

  Monoid lazy_throw(Monoid from,Monoid to){
    return to + from / 2;
  }

  LazySegment(const vector<Monoid> init, Monoid ide_, Monoid lazy_i)
      : ide(ide_), lazy_init(lazy_i) {
    n = 1;
    int sz = init.size();
    while (n < sz) n *= 2;

    node.resize(n * 2 - 1, ide);
    lazy.resize(n * 2 - 1, lazy_init);
    lazyFlag.resize(n * 2 - 1, false);

    for (int i = 0; i < sz; i++) node[i + n - 1] = init[i];
    for (int i = n - 2; i >= 0; i--)
      node[i] = func(node[i * 2 + 1], node[i * 2 + 2]);
  }

  void eval(int k, int l, int r) {
    if (lazyFlag[k]) {
      node[k] = lazy_effect(node[k], lazy[k]);

      if (r - l > 1) {
        lazy[2 * k + 1] = lazy_throw(lazy[k], lazy[2 * k + 1]);
        lazy[2 * k + 2] = lazy_throw(lazy[k], lazy[2 * k + 2]);
        lazyFlag[2 * k + 1] = true;
        lazyFlag[2 * k + 2] = true;
      }

      lazyFlag[k] = false;
      lazy[k] = lazy_init;
    }
  }

  void update_inter(int a, int b, Monoid x, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;

    eval(k, l, r);

    if (r <= a || b <= l) return;

    if (a <= l && r <= b) {
      lazy[k] = lazy_make(l, r, x, lazy[k]);
      lazyFlag[k] = true;
      eval(k, l, r);
    } else {
      update_inter(a, b, x, k * 2 + 1, l, (l + r) / 2);
      update_inter(a, b, x, k * 2 + 2, (l + r) / 2, r);
      node[k] = func(node[k * 2 + 1], node[k * 2 + 2]);
    }
  }

  Monoid get_inter(int a, int b, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;

    eval(k, l, r);

    if (r <= a || b <= l) return ide;

    if (a <= l && r <= b) return node[k];

    Monoid lm = get_inter(a, b, k * 2 + 1, l, (l + r) / 2);
    Monoid rm = get_inter(a, b, k * 2 + 2, (l + r) / 2, r);
    return func(lm, rm);
  }
};

#include <iostream>

using i64 = long long;

struct HLDecomposition{
  int n,pos;
  vector<vector<int> > G;
  vector<int> vid,head,hvy,par,dep,inv,sub;

  LazySegment<i64> seg;

  HLDecomposition(int sz):
    n(sz),pos(0),G(n),
    vid(n,-1),head(n),hvy(n,-1),
    par(n),dep(n),inv(n),sub(n,1),seg(vector<i64>(n,0),0,0){}
  
  void add_edge(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
  }

  void dfs(int rt){
    typedef pair<int,int> T;
    stack<T> st;
    par[rt] = -1;
    dep[rt] = 0;
    st.push(make_pair(rt,0));
    while(!st.empty()){
      int v= st.top().first;
      int &i = st.top().second;
      if(i < (int)G[v].size()){
        int u = G[v][i++];
        if(u == par[v]) continue;
        par[u] = v;
        dep[u] = dep[v] + 1;
        st.push(make_pair(u,0));
      }
      else{
        st.pop();
        int res = 0;
        for(int i = 0;i < (int)G[v].size();i++){
          int u = G[v][i];
          if(u == par[v]) continue;
          sub[v] += sub[u];
          if(res < sub[u]) res = sub[u],hvy[v] = u;
        }
      }
    }
  }

  void bfs(int r){
    int &k = pos;
    queue<int> q;
    q.push(r);
    while(!q.empty()){
      int h = q.front();
      q.pop();
      for(int i = h;i != -1;i = hvy[i]){
        vid[i] = k++;
        inv[vid[i]] = i;
        head[i] = h;
        for(int j = 0;j < (int)G[i].size();j++){
          int u = G[i][j];
          if(u != par[i] && u != hvy[i]) q.push(u);
        }
      }
    }
  }

  void build(int r){
    dfs(r);
    bfs(r);
  }

  void f(int l,int r){
    seg.update_inter(l,r + 1,1);
  }

  void for_vertex(int u,int v){
    while(1){
      if(vid[u] > vid[v]) swap(u,v);
      f(max(vid[head[v]],vid[u]),vid[v]);
      if(head[u] != head[v]) v= par[head[v]];
      else break;
    }
  }


  void for_edge(int u,int v){
    while(1){
      if(vid[u],vid[v]) swap(u,v);
      if(head[u] != head[v]){
        f(vid[head[v]],vid[v]);
        v = par[head[v]];
      }
      else{
        if(u != v) f(vid[u] + 1,vid[v]);
        break;
      }
    }
  }

  int lca(int u,int v){
    while(1){
      if(vid[u] > vid[v]) swap(u,v);
      if(head[u] == head[v])
        return u;
      v = par[head[v]];
    }
  }

  int distance(int u,int v){
    return dep[u] + dep[v] - 2 * dep[lca(u,v)];
  }
};

#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main(){
  int N;
  cin >> N;
  HLDecomposition hld(N);
  rep(i,0,N - 2){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    hld.add_edge(a,b);
  }
  hld.build(0);
  int Q;
  cin >> Q;
  rep(i,0,Q - 1){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    hld.for_vertex(a,b);
  }

  i64 ans = 0;
  rep(i,0,N - 1){
    i64 a = hld.seg.get_inter(i,i + 1);
    ans += a * (a + 1) / 2;
  }

  cout << ans << endl;
}
0