結果

問題 No.399 動的な領主
コンテスト
ユーザー 萃罰
提出日時 2024-08-08 06:28:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 757 ms / 2,000 ms
コード長 6,483 bytes
コンパイル時間 7,743 ms
コンパイル使用メモリ 336,428 KB
実行使用メモリ 27,264 KB
最終ジャッジ日時 2024-08-08 06:28:50
合計ジャッジ時間 13,345 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<vvvll> vvvvll;
typedef vector<vvvvll> vvvvvll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef vector<char> vc;
typedef vector<vc> vvc;
using Graph1 = vector<vector<int>>;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rrep(i,a,n) for(ll i=a;i<n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define pper(i,a,n) for(ll i=n-1;i>=a;i--)
#define fs first
#define sc second
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend() 
const ll INF = 1LL<<60;
const int mod1 = 1000000007;
const int mod2 = 998244353;
//最大更新、最小更新
template<class T>bool chmax(T& x,T y){if(x<y){x=y;return true;}else return false;}
template<class T>bool chmin(T & x,T y){if(x>y){x = y;return true;}else return false;}
template<typename T> using pq = priority_queue<T>;
template<typename T> using pqg = priority_queue<T,vector<T>,greater<T>>;
using mint = modint998244353;

class HLD{
    private:
        int V;
        vvll g;
        vll stsize,parent,pathtop,in,out;
        int root;
        void BuildStsize(int u,int p){
            stsize[u] = 1;parent[u] = p;
            for(ll &v:g[u]){
                if(v==p){
                    if(v==g[u].back()) break;
                    else swap(v,g[u].back());
                }
                BuildStsize(v,u);
                stsize[u]+=stsize[v];
                if(stsize[v]>stsize[g[u][0]]){
                    swap(v,g[u][0]);
                }
            }
        }
        void BuildPath(int u, int p, int& tm){
            in[u] = tm++;
            for(ll v:g[u]){
                if(v == p) continue;
                pathtop[v] = (v == g[u][0] ? pathtop[u] : v);
                BuildPath(v, u, tm);
            }
            out[u] = tm;
        }
    public:
        void add_edge(int u,int v){
            g[u].push_back(v),g[v].push_back(u);
        }
        void build(int _root){
            root = _root;
            int tm = 0;
            BuildStsize(root,-1);
            pathtop[root] = root;
            BuildPath(root,-1,tm);
        }
        inline int get(int a){
            return in[a];
        }
        int lca(int a,int b){
            int pa = pathtop[a],pb=pathtop[b];
            while(pathtop[a]!=pathtop[b]){
                if(in[pa]>in[pb]){
                    a = parent[pa],pa = pathtop[a];
                }
                else{
                    b=parent[pb],pb=pathtop[b];
                }
            }
            if(in[a]>in[b])swap(a,b);
            return a;
        }
        void subtree_query(int a,const function<void(int,int)> &func){
            func(in[a],out[a]);
        }
        void path_query(int a,int b,const function<void(int,int)> &func){
            int pa = pathtop[a],pb=pathtop[b];
            while(pathtop[a]!=pathtop[b]){
                if(in[pa]>in[pb]){
                    func(in[pa],in[a]);
                    a=parent[pa],pa=pathtop[a];
                }
                else{
                    func(in[pb],in[b]);
                    b=parent[pb],pb=pathtop[b];
                }
            }
            if(in[a]>in[b]) swap(a,b);
            func(in[a],in[b]);
        }
        HLD(int node) :V(node),g(V),stsize(V,0),parent(V,-1),pathtop(V,-1),in(V,-1),out(V,-1){}
};

template<typename T> class segtre {
private:
    int n,sz,h; vector<T> node, lazy_update, lazy_add; vector<bool> lazyFlag;
public:
    segtre(vector<T> v) : n(1), sz((int)v.size()), h(0){
        while(n < sz) n *= 2, h++;
        node.resize(2*n, 0);
        lazy_update.resize(2*n, 0); lazyFlag.resize(2*n, false);
        lazy_add.resize(2*n, 0);
        for(int i = 0; i < sz; i++) node[i+n] = v[i];
        for(int i=n-1; i>=1; i--) node[i] = node[2*i] + node[2*i+1];
    }
    void eval(int k) {
        if(lazyFlag[k]){
            lazy_update[k] += lazy_add[k];
            node[k] = lazy_update[k];
            if(k < n) {
                lazy_add[2*k] = lazy_add[2*k+1] = 0;
                lazy_update[2*k] = lazy_update[2*k+1] = lazy_update[k] / 2;
                lazyFlag[2*k] = lazyFlag[2*k+1] = true;
            }
            lazy_add[k] = 0, lazyFlag[k] = false;
        }else if(lazy_add[k] != 0){
            node[k] += lazy_add[k];
            if(k < n){
                lazy_add[2*k] += lazy_add[k] / 2; lazy_add[2*k+1] += lazy_add[k] / 2;
            }
            lazy_add[k] = 0;
        }
    }
    void update(int a, int b, T x, int k=1, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy_add[k] = 0; lazy_update[k] = x*(r-l); lazyFlag[k] = true; eval(k);
        }else{
            update(a, b, x, 2*k, l, (l+r)/2); update(a, b, x, 2*k+1, (l+r)/2, r);
            node[k] = node[2*k] + node[2*k+1];
        }
    }
    void add(int a, int b, T x, int k=1, int l=0, int r=-1){
        if(r < 0) r = n;
        eval(k);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy_add[k] += x*(r-l); eval(k);
        }else{
            add(a, b, x, 2*k, l, (l+r)/2); add(a, b, x, 2*k+1, (l+r)/2, r);
            node[k] = node[2*k] + node[2*k+1];
        }
    }
    T query(int a, int b) {
        a += n, b += n - 1;
        for(int i = h; i > 0; i--) eval(a >> i), eval(b >> i);
        b++;
        T res1 = 0, res2 = 0;
        while(a < b) {
            if(a & 1) eval(a), res1 += node[a++];
            if(b & 1) eval(--b), res2 += node[b];
            a >>= 1, b >>= 1;
        }
        return res1 + res2;
    }
    void print(){for(int i = 0; i < sz; i++)cout<<query(i,i+1)<< " ";cout<<endl;}
};

int main(){
    int n;cin >> n;
    HLD hl(n);
    vvll gr(n);
    rep(i,n-1){
        int u,v;cin >> u >>v;
        --u,--v;
        hl.add_edge(u,v);
    }
    hl.build(0);
    segtre seg(vll(n,0));
    int q;cin >>q;
    ll sum = 0;
    rep(i,q){
        int u,v;cin >> u >> v;
        hl.path_query(u-1,v-1,[&](int k,int l){
            seg.add(k,l+1,1);
            sum += seg.query(k,l+1);
            });
    }
    cout << sum<<endl;
}
0