結果

問題 No.399 動的な領主
ユーザー yosupotyosupot
提出日時 2016-07-15 22:25:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 351 ms / 2,000 ms
コード長 4,961 bytes
コンパイル時間 980 ms
コンパイル使用メモリ 105,420 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-11-07 18:32:49
合計ジャッジ時間 5,102 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
8,704 KB
testcase_01 AC 5 ms
8,832 KB
testcase_02 AC 5 ms
8,832 KB
testcase_03 AC 5 ms
8,960 KB
testcase_04 AC 7 ms
8,960 KB
testcase_05 AC 30 ms
8,960 KB
testcase_06 AC 351 ms
8,832 KB
testcase_07 AC 342 ms
8,832 KB
testcase_08 AC 338 ms
8,832 KB
testcase_09 AC 339 ms
8,832 KB
testcase_10 AC 8 ms
8,960 KB
testcase_11 AC 23 ms
8,832 KB
testcase_12 AC 238 ms
8,960 KB
testcase_13 AC 233 ms
8,832 KB
testcase_14 AC 118 ms
10,496 KB
testcase_15 AC 216 ms
10,496 KB
testcase_16 AC 237 ms
9,600 KB
testcase_17 AC 337 ms
8,832 KB
testcase_18 AC 341 ms
8,832 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int TEN(int n) {return (n==0)?1:10*TEN(n-1);}

/**
 * Link-Cut Tree
 *
 * 機能としては、link、cut、evert、parent, rootを実装済み
 * 辺に値を持たせたい場合は頂点倍加
 */
struct LCNode {
    using NP = LCNode*;
    static NP last;

    ll d, dsm, dlz;
    NP init_last() {
        sz = 0; // Important
        d = 0; dsm = 0; dlz = 0;
        return this;
    }
    void init_node() {
        sz = 1; rev = false; // Important
        d = dsm = 1; dlz = 0;
    }
    void update() {
        sz = 1 + l->sz + r->sz; // Important
        dsm = d + l->dsm + r->dsm;
    }
    void addch(NP b) {
        assert(b == last || b->p == this);
    }
    void delch(NP b) {
        assert(b == last || b->p == this);
    }
    void push() {
        assert(this != last);
        if (rev) { // Important
            if (l != last) {
                l->revdata();
            }
            if (r != last) {
                r->revdata();
            }
            rev = false;
        }
        if (dlz) {
            if (l != last) {
                l->lzdata(dlz);
            }
            if (r != last) {
                r->lzdata(dlz);
            }
            dlz = 0;
        }
    }
    void revdata() {
        rev ^= true; swap(l, r); // Important
    }
    void lzdata(int x) {
        d += x;
        dsm += x * sz;
        dlz += x;
    }
    //ここから
    NP p, l, r;
    int sz;
    bool rev;
    LCNode() : p(nullptr), l(last), r(last) {}
    inline int pos() {
        if (p) {
            if (p->l == this) return -1;
            if (p->r == this) return 1;
        }
        return 0;
    }
    void rot() {
        NP q = p->p;
        int pps = p->pos();
        if (pps == -1) {
            q->l = this;
        }
        if (pps == 1) {
            q->r = this;
        }
        if (p->l == this) {
            p->l = r;
            if (r) r->p = p;
            r = p;
        } else {
            p->r = l;
            if (l) l->p = p;
            l = p;
        }
        p->p = this;
        p->update();
        update();
        p = q;
        if (q) q->update();
    }
    void splay() {
        supush();
        int ps;
        while ((ps = pos())) {
            int pps = p->pos();
            if (!pps) {
                rot();
            } else if (ps == pps) {
                p->rot(); rot();
            } else {
                rot(); rot();
            }
        }
    }
    void expose() {
        for (NP u = this; u; u = u->p) {
            u->splay();
        }
        for (NP u = this, ur = last; u; u = u->p) {
            NP tmp = u->r;
            u->r = last;
            u->update();
            u->addch(tmp);
            u->delch(ur);
            u->r = ur;
            u->update();
            ur = u;
        }
        splay();
    }
    void supush() {
        if (pos()) {
            p->supush();
        }
        push();
    }
    //ここまでは絶対必要

    void link(NP r) {
        expose();
        r->expose();
        p = r;
        r->addch(this);
    }

    NP parent() {
        expose();
        NP u = this->l;
        if (u == last) return last;
        u->push();
        while (u->r != last) {
            u = u->r;
            u->push();
        }
        u->expose();
        return u;
    }

    void cut() {
        NP u = parent();
        assert(u != last);
        assert(u->r == last);
        this->splay();
        u->delch(this);
        this->p = nullptr;
    }

    NP root() {
        expose();
        NP u = this;
        while (u->l != last) {
            u = u->l;
            u->push();
        }
        u->expose();
        return u;
    }

    void evert() {
        expose();
        revdata();
    }

    NP lca(NP n) {
        n->expose();
        expose();
        NP t = n;
        while (n->p != nullptr) {
            if (!n->pos()) t = n->p;
            n = n->p;
        }
        return (this == n) ? t : nullptr;
    }
};
LCNode::NP LCNode::last = (new LCNode())->init_last();

const int MN = 100100;
LCNode lc[MN];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        lc[i].init_node();
    }
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        lc[a].evert();
        lc[a].link(lc+b);
    }
    int q;
    cin >> q;
    ll ans = 0;
    for (int i = 0; i < q; i++) {
        int a, b; 
        cin >> a >> b; a--; b--;
        lc[a].evert();
        lc[b].expose();
        ans += lc[b].dsm;
        lc[b].lzdata(1);
    }
    cout << ans << endl;
    return 0;
}
0