結果

問題 No.399 動的な領主
ユーザー hashiryohashiryo
提出日時 2019-05-31 14:19:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 188 ms / 2,000 ms
コード長 3,312 bytes
コンパイル時間 1,567 ms
コンパイル使用メモリ 170,508 KB
実行使用メモリ 18,560 KB
最終ジャッジ日時 2024-09-17 16:12:50
合計ジャッジ時間 5,096 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 14 ms
6,944 KB
testcase_06 AC 174 ms
13,016 KB
testcase_07 AC 169 ms
12,928 KB
testcase_08 AC 184 ms
13,184 KB
testcase_09 AC 180 ms
13,056 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 10 ms
6,940 KB
testcase_12 AC 133 ms
13,440 KB
testcase_13 AC 125 ms
13,440 KB
testcase_14 AC 61 ms
18,560 KB
testcase_15 AC 64 ms
18,560 KB
testcase_16 AC 86 ms
15,872 KB
testcase_17 AC 188 ms
12,928 KB
testcase_18 AC 176 ms
13,056 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pll;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

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

    T operator[](const int k){return sum(k+1)-sum(k);}
};

struct HLDecomposition{
private:
    int t;
    void dfs_size(int v=0){
        size[v]=1;
        for(int& u:g[v]){
            if(par[u]>=0){
                swap(u,g[v].back());
                if(u==g[v].back())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;
    }
public:
    int V;
    vector<vector<int>> g;
    vector<int> dep,par,head,size,inv;
    vector<int> in,out;
    HLDecomposition(int size_)
    :t(0),V(size_),g(V),dep(V,0),par(V,-1),head(V),size(V),inv(V),in(V),out(V){}

    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)];
    }

    int operator[](const int &k){
        return in[k];
    }
};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N;cin>>N;
  HLDecomposition hld(N);
  for(ll i=0;i<N-1;i++){
    ll 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);
  ll Q;cin>>Q;
  ll ans =0;
  for(ll q=0;q<Q;q++){
    ll A,B;cin>>A>>B;A--;B--;
    ll u=A,v=B;
    while(1){
        if(hld[u]>hld[v])swap(u,v);
        ans += bit.sum(hld[v]+1)-bit.sum(max(hld[hld.head[v]],hld[u]));
        if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]];
        else break;
    }
    u=A,v=B;
    while(1){
        if(hld[u]>hld[v])swap(u,v);
        bit.add_interval(max(hld[hld.head[v]],hld[u]),hld[v]+1,1);
        if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]];
        else break;
    }
  }
  cout<<ans<<endl;
  return 0;
}
0