結果

問題 No.399 動的な領主
ユーザー onakasuitacityonakasuitacity
提出日時 2023-05-10 09:38:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 583 ms / 2,000 ms
コード長 5,599 bytes
コンパイル時間 2,578 ms
コンパイル使用メモリ 219,472 KB
実行使用メモリ 11,344 KB
最終ジャッジ日時 2024-05-04 23:27:27
合計ジャッジ時間 8,769 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 5 ms
6,940 KB
testcase_05 AC 42 ms
6,944 KB
testcase_06 AC 511 ms
10,120 KB
testcase_07 AC 506 ms
10,280 KB
testcase_08 AC 517 ms
10,156 KB
testcase_09 AC 479 ms
10,184 KB
testcase_10 AC 6 ms
6,944 KB
testcase_11 AC 28 ms
6,944 KB
testcase_12 AC 344 ms
10,224 KB
testcase_13 AC 327 ms
10,204 KB
testcase_14 AC 71 ms
11,344 KB
testcase_15 AC 265 ms
11,216 KB
testcase_16 AC 324 ms
10,324 KB
testcase_17 AC 583 ms
9,984 KB
testcase_18 AC 506 ms
10,228 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;using ll=int_fast64_t;using ld=long double;constexpr ll INF=1LL<<60;
void solve();int main(){cin.tie(nullptr);ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);solve();return 0;}
#define SELECTOR(_1,_2,_3,_4,SELECT,...) SELECT
#define rep(...) SELECTOR(__VA_ARGS__,_rep2,_rep1,_rep0)(__VA_ARGS__)
#define _rep0(i,n) for(ll i=0;i<(ll)n;++i)
#define _rep1(i,k,n) for(ll i=k;i<(ll)n;++i)
#define _rep2(i,k,n,d) for(ll i=k;d>0?i<(ll)n:i>(ll)n;i+=d)
template<class T> inline bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
#ifdef DEBUG
#include "memo/dump.hpp"
#else
#define dump(...)
#endif

template<class M>
class LinkCutTree{
public:
    using T = typename M::T;
    using E = typename M::E;
    struct Node{
        Node *left = nullptr, *right = nullptr, *parent = nullptr;
        T value, sum;
        E lazy = M::id;
        int size = 1;
        bool reverse = false;
        Node(){}
        Node(T value) : value(value), sum(value){}
        bool push(){
            if(lazy != M::id){
                value = M::act(lazy, value, 1);
                sum = M::act(lazy, sum, size);
                if(left) left->lazy = M::compose(left->lazy, lazy);
                if(right) right->lazy = M::compose(right->lazy, lazy);
                lazy = M::id;
            }
            if(reverse){
                swap(left, right);
                if(left) left->reverse ^= true;
                if(right) right->reverse ^= true;
                reverse = false;
                return true;
            }
            return false;
        }
        void update(){
            size = 1, sum = value;
            if(left) left->push(), size += left->size, sum = M::dot(left->sum, sum);
            if(right) right->push(), size += right->size, sum = M::dot(sum, right->sum);
        }
    };
private:
    Node* array;
    void rotate(Node* v, Node* p, bool d){
        if(d){
            p->left = v->right;
            if(v->right) v->right->parent = p;
            v->right = p;
        }else{
            p->right = v->left;
            if(v->left) v->left->parent = p;
            v->left = p;
        }
        p->parent = v;
        p->update();
    }
    void splay(Node* v){
        vector<Node*> path;
        vector<char> direction;
        for(Node* u = v;; u = u->parent){
            Node* p = u->parent;
            if(!p || (p->left != u && p->right != u)){
                v->parent = p;
                break;
            }
            path.push_back(p);
            direction.push_back(u == p->left);
        }
        reverse(path.begin(), path.end());
        reverse(direction.begin(), direction.end());
        rep(i, path.size()) direction[i] ^= path[i]->push();
        v->push();
        while(path.size() >= 2){
            Node* p = path.back(); path.pop_back();
            Node* g = path.back(); path.pop_back();
            bool dp = direction.back(); direction.pop_back();
            bool dg = direction.back(); direction.pop_back();
            if(dp == dg) rotate(p, g, dg), rotate(v, p, dp);
            else rotate(v, p, dp), rotate(v, g, dg);
        }
        if(!path.empty()){
            Node* p = path.back(); path.pop_back();
            bool d = direction.back(); direction.pop_back();
            rotate(v, p, d);
        }
    }
    Node* expose(Node* v){
        Node *prev = nullptr;
        for(Node* cur = v; cur; cur = cur->parent){
            splay(cur);
            cur->right = prev;
            prev = cur;
        }
        splay(v);
        v->update();
        return prev;
    }
    void evert(Node* v){expose(v); v->reverse ^= true;}
    Node* lca(Node* u, Node* v){expose(u); return expose(v);}
    void link(Node* u, Node* v){evert(u); u->parent = v;}
    void cut(Node* v){
        expose(v);
        v->left->parent = nullptr, v->left = nullptr;
        v->update();
    }
    bool is_connected(Node* u, Node* v){
        if(u == v) return true;
        expose(u), expose(v);
        return u->parent;
    }
    int depth(Node* v){expose(v); return v->size - 1;}
    void act(Node* u, Node* v, E f){evert(u), expose(v), v->lazy = M::compose(v->lazy, f);}
    T sum(Node* u, Node* v){evert(u), expose(v); return v->sum;}
public:
    LinkCutTree(vector<T> A){
        array = new Node[A.size()];
        rep(i, A.size()) array[i] = Node(A[i]);
    }
    ~LinkCutTree(){delete[] array;}
    void evert(int i){evert(&array[i]);}
    int lca(int i, int j){return lca(&array[i], &array[j]) - array;}
    void link(int i, int j){link(&array[i], &array[j]);}
    void cut(int i){cut(&array[i]);}
    bool is_connected(int i, int j){return is_connected(&array[i], &array[j]);}
    int depth(int i){return depth(&array[i]);}
    void act(int i, int j, E f){act(&array[i], &array[j], f);}
    T sum(int i, int j){return sum(&array[i], &array[j]);}
};

struct monoid{
    using T = ll;
    using E = ll;
    static const T e = 0;
    static T dot(T x, T y){return x + y;}
    static E compose(E f, E g){return f + g;}
    static const E id = 0;
    static T act(E f, T x, int size){return x + f * size;}
};

void solve(){
    int N; cin >> N;
    vector<ll> A(N, 1);
    LinkCutTree<monoid> tree(A);
    rep(_, N - 1){
        int u, v; cin >> u >> v;
        u--, v--;
        tree.link(u, v);
    }

    ll ans = 0;
    int Q; cin >> Q;
    while(Q--){
        int u, v; cin >> u >> v;
        u--, v--;
        ans += tree.sum(u, v);
        tree.act(u, v, 1);
    }
    cout << ans << '\n';
}
0