結果

問題 No.386 貪欲な領主
ユーザー yosupotyosupot
提出日時 2016-07-01 22:47:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 519 ms / 2,000 ms
コード長 4,726 bytes
コンパイル時間 603 ms
コンパイル使用メモリ 70,676 KB
実行使用メモリ 9,508 KB
最終ジャッジ日時 2023-08-02 08:55:24
合計ジャッジ時間 4,103 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
8,252 KB
testcase_01 AC 4 ms
7,944 KB
testcase_02 AC 4 ms
8,104 KB
testcase_03 AC 4 ms
8,092 KB
testcase_04 AC 519 ms
9,508 KB
testcase_05 AC 436 ms
7,924 KB
testcase_06 AC 442 ms
8,116 KB
testcase_07 AC 7 ms
8,216 KB
testcase_08 AC 61 ms
8,008 KB
testcase_09 AC 11 ms
7,952 KB
testcase_10 AC 4 ms
7,920 KB
testcase_11 AC 4 ms
7,920 KB
testcase_12 AC 5 ms
8,188 KB
testcase_13 AC 15 ms
8,064 KB
testcase_14 AC 456 ms
7,924 KB
testcase_15 AC 435 ms
9,508 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cassert>

using namespace std;
using ll = long long;
constexpr ll TEN(int n) { return (!n) ? 1 : 10 * TEN(n-1); }
 
template <class E>
using Graph = vector<vector<E>>;

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

    ll d;
    ll dsm;
    NP init_last() {
        sz = 0; // Important
        d = dsm = 0;
        return this;
    }
    void init_node() {
        sz = 1; rev = false; // Important
        d = dsm = 0;
    }
    void update() {
        sz = 1 + l->sz + r->sz; // Important
        dsm = d + l->dsm + r->dsm;
    }
    void set(int d) {
        this->d = d;
        update();
    }
    void push() {
        assert(this != last);
        if (rev) { // Important
            if (l != last) {
                l->revdata();
            }
            if (r != last) {
                r->revdata();
            }
            rev = false;
        }
    }
    void revdata() {
        rev ^= true; swap(l, r); // Important
    }
    void addch(NP b) {
        assert(b == last || b->p == this);
    }
    void delch(NP b) {
        assert(b == last || b->p == this);
    }

    //ここから
    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 = 100200;
LCNode lc[MN];

int main() {
    int n;
    cin >> n;
    assert(2 <= n and n <= 100000);
    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;
        lc[a].evert();
        lc[a].link(lc+b);
    }
    for (int i = 0; i < n; i++) {
        int u;
        cin >> u;
        lc[i].evert();
        lc[i].set(u);
    }

    int m;
    cin >> m;
    ll ans = 0;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c; 
        assert(a != b);
        lc[a].evert();
        lc[b].expose();
        ans += lc[b].dsm * c;
    }
    cout << ans << endl;
    return 0;
}
0