結果

問題 No.399 動的な領主
ユーザー hashiryohashiryo
提出日時 2018-10-10 14:08:09
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 269 ms / 2,000 ms
コード長 3,292 bytes
コンパイル時間 878 ms
コンパイル使用メモリ 95,112 KB
実行使用メモリ 18,048 KB
最終ジャッジ日時 2024-04-20 19:26:18
合計ジャッジ時間 4,984 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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 3 ms
5,376 KB
testcase_05 AC 21 ms
5,376 KB
testcase_06 AC 269 ms
13,056 KB
testcase_07 AC 251 ms
13,056 KB
testcase_08 AC 249 ms
13,056 KB
testcase_09 AC 261 ms
12,928 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 17 ms
5,376 KB
testcase_12 AC 209 ms
13,568 KB
testcase_13 AC 209 ms
13,440 KB
testcase_14 AC 125 ms
18,048 KB
testcase_15 AC 132 ms
18,048 KB
testcase_16 AC 164 ms
15,616 KB
testcase_17 AC 263 ms
12,928 KB
testcase_18 AC 255 ms
12,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ull INF = ULLONG_MAX;
const ll MOD = 998244353;

struct HLDecomposition{
public:
  int V;
  vector<vint> g;
  vint dep,par,head,size,inv;
  vint in,out;
  HLDecomposition(int size_)
  :V(size_),g(V),dep(V,0),par(V,-1),head(V),size(V),inv(V),in(V),out(V),t(0){}

  void add_edge(int u,int v){
    g[u].push_back(v);
    g[v].push_back(u);
  }
  void build(int root=0){
    par[root]=0;
    dfs_size(root);
    par[root]=-1;
    dfs_hld(root);
  }

  int lca(int u,int v){
    while(1){
      if(in[u]>in[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)];
  }
private:
  int t;
  void dfs_size(int v=0){
    size[v]=1;
    for(int& u:g[v]){
      if(par[u]>=0)continue;
      par[u]=v;
      dfs_size(u);
      size[v]+=size[u];
      if(size[u]>size[g[v][0]]){
        swap(u,g[v][0]);
      }
    }
  }
  void dfs_hld(int v=0){
    in[v] = t++;
    inv[in[v]]=v;
    for(int& u:g[v]){
      if(par[u]!=v)continue;
      head[u]=(u==g[v][0]?head[v]:u);
      dfs_hld(u);
    }
    out[v]=t;
  }
};

template <class T>
struct BIT_interval {
    vector<T> dat1;
    vector<T> dat2;
    BIT_interval(int n) : dat1(n+1),dat2(n+1) { }
    // add w [l,r)
    void add_interval(int l,int r, T w) {
        for (int k=l+1; k < dat1.size(); k += k&-k) dat1[k] -= w*l;
        for (int k=r+1; k < dat1.size(); k += k&-k) dat1[k] += w*r;
        for (int k=l+1; k < dat2.size(); k += k&-k) dat2[k] += w;
        for (int k=r+1; k < dat2.size(); k += k&-k) dat2[k] -= w;
    }
    T sum(int x) {
        T s = 0;
        for (int k=x; k > 0; k &= k-1) s += dat1[k];
        for (int k=x; k > 0; k &= k-1) s += dat2[k]*x;
        return s;
    }
};




int main(){
  int N;cin>>N;
  HLDecomposition hld(N);
  repeat(i,N-1){
    int u,v;cin>>u>>v;u--;v--;
    hld.add_edge(u,v);
  }
  hld.build();
  BIT_interval<ll> bit(N);
  bit.add_interval(0,N,1);
  int Q;cin>>Q;
  ll ans = 0;
  repeat(q,Q){
    int A,B;cin>>A>>B;A--;B--;
    int u=A,v=B;
    while(1){
      if(hld.in[u]>hld.in[v])swap(u,v);
      ans += bit.sum(hld.in[v]+1)-bit.sum(max(hld.in[hld.head[v]],hld.in[u]));
      if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]];
      else break;
    }
    u=A,v=B;
    while(1){
      if(hld.in[u]>hld.in[v])swap(u,v);
      bit.add_interval(max(hld.in[hld.head[v]],hld.in[u]),hld.in[v]+1,1);
      if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]];
      else break;
    }
  }
  cout << ans << endl;
  return 0;
}
0