結果

問題 No.399 動的な領主
ユーザー uenokuuenoku
提出日時 2018-01-19 04:16:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,015 ms / 2,000 ms
コード長 8,425 bytes
コンパイル時間 3,233 ms
コンパイル使用メモリ 214,268 KB
実行使用メモリ 48,624 KB
最終ジャッジ日時 2024-06-06 16:52:35
合計ジャッジ時間 13,196 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 60 ms
7,020 KB
testcase_06 AC 1,015 ms
38,776 KB
testcase_07 AC 909 ms
38,780 KB
testcase_08 AC 907 ms
38,592 KB
testcase_09 AC 881 ms
38,568 KB
testcase_10 AC 7 ms
5,376 KB
testcase_11 AC 43 ms
7,052 KB
testcase_12 AC 602 ms
37,988 KB
testcase_13 AC 559 ms
38,116 KB
testcase_14 AC 263 ms
48,624 KB
testcase_15 AC 338 ms
48,496 KB
testcase_16 AC 420 ms
42,880 KB
testcase_17 AC 940 ms
38,436 KB
testcase_18 AC 910 ms
38,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
struct segtree {
    vector<lli> dat, lazy;
    int n;
    lli unit = 0;
    segtree(int N)
    {
        n = 1;
        while (N > n) {
            n *= 2;
        }
        dat.assign(2 * n - 1, unit);
        lazy.assign(2 * n - 1, unit);
    }
    void eval(int k)
    {
        if (lazy[k] == 0)
            return;
        dat[k] += lazy[k];
        if (n - 1 > k) {
            lazy[2 * k + 1] += lazy[k] / 2;
            lazy[2 * k + 2] += lazy[k] / 2;
        }
        lazy[k] = 0;
    }
    void update(int a, lli x)
    {
        add(a, a + 1, x, 0, 0, n);
    }
    void add(int a, int b, lli x)
    {
        add(a, b, x, 0, 0, n);
    }
    void add(int a, int b, lli x, int k, int l, int r)
    {
        eval(k);
        if (b <= l || r <= a)
            return;
        if (a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k);
        } else {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            dat[k] = dat[2 * k + 1] + dat[2 * k + 2];
        }
    }
    lli query(int a, int b, int k, int l, int r)
    {
        eval(k);
        if (b <= l || r <= a)
            return 0;
        if (a <= l and r <= b)
            return dat[k];
        lli vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        lli vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }
    lli query(int a, int b)
    {
        return query(a, b, 0, 0, n);
    }
};


struct hldec {
    using T = lli;
    int n;
    int col = 0;
    vector<vector<int>> e;
    vector<vector<int>> heavy;
    vector<vector<int>> light;
    vector<vector<T>> cls;
    vector<T> vers;
    vector<pair<int, int>> pos;
    vector<pair<int, int>> par;
    map<pair<int, int>, int> dict;
    bool builded = false;
    vector<segtree> vec_seg;
    int root = 0;
    T unit = 0;
    vector<int> size;
    T f(T a, T b) { return a + b; }  //add
    hldec(int n, vector<T> vers, int root = 0) : n(n), root(root), vers(vers)
    {
        e.assign(n, {});
        par.assign(n, make_pair(-1, -1));
        heavy.assign(n, {});
        light.assign(n, {});
        size.assign(n, 0);
        pos.assign(n, make_pair(-1, -1));
        cls.assign(n, {});
    }
    void add(int u, int v)
    {
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int sub_tree_size(int cur, int par)
    {
        int tmp = 1;
        for (auto s : e[cur]) {
            if (par != s) {
                tmp += sub_tree_size(s, cur);
            }
        }
        size[cur] = tmp;
        return tmp;
    }
    void dfs_label(int cur, int par)
    {
        lli idx = -1;
        lli mem = 0;
        rep(i, e[cur].size())
        {
            auto s = e[cur][i];
            if (s != par) {
                if (size[s] > mem) {
                    mem = size[s];
                    idx = i;
                }
            }
        }
        if (idx == -1)
            return;
        rep(i, e[cur].size())
        {
            auto s = e[cur][i];
            if (s != par) {
                if (idx == i) {
                    heavy[cur].push_back(s);
                } else {
                    light[cur].push_back(s);
                }
                dfs_label(s, cur);
            }
        }
    }
    void edge_labeling()
    {
        sub_tree_size(root, -1);
        dfs_label(root, -1);
    }
    void dfs_arrays(int cur, int c)
    {
        cls[c].push_back(vers[cur]);
        int idx = cls[c].size() - 1;
        pos[cur] = make_pair(c, cls[c].size() - 1);
        dict[pos[cur]] = cur;

        for (auto s : heavy[cur]) {
            dfs_arrays(s, c);
        }
        for (auto s : light[cur]) {
            col++;
            par[col] = make_pair(c, idx);
            dfs_arrays(s, col);
        }
    }
    void make_arrays()
    {
        dfs_arrays(root, 0);
    }
    void build_segtree()
    {
        rep(j, cls.size())
        {
            auto& s = cls[j];
            int size = s.size();
            segtree seg(size);
            rep(i, size)
            {
                seg.update(i, s[i]);
            }
            vec_seg.push_back(seg);
        }
    }
    void build(bool opt = false)
    {
        edge_labeling();
        if (opt) {
            e.clear();
        }
        cerr << "labeled done" << endl;
        make_arrays();

        cerr << "arrays" << endl;
        if (opt) {
            heavy.clear();
            light.clear();
        }

        build_segtree();
        builded = true;

        cerr << "seg_build" << endl;
    }
    void add(int u, int v, T x)
    {
        if (!builded) {
            cout << "HOGE" << endl;
            build();
            builded = true;
        }
        vector<pair<int, int>> hist_u;
        vector<pair<int, int>> hist_v;
        rep(j, 2)
        {
            int tmp = j == 1 ? u : v;
            while (true) {
                int cur_col = pos[tmp].first;
                if (j)
                    hist_u.push_back(pos[tmp]);
                else
                    hist_v.push_back(pos[tmp]);
                if (cur_col == 0)
                    break;
                tmp = dict[par[cur_col]];
            }
        }
        int pivot = 0;
        T ans = unit;
        set<int> hist_u_set;
        map<int, int> post;
        for (auto s : hist_u) {
            hist_u_set.insert(s.first);
            post[s.first] = s.second;
        }
        rep(i, hist_v.size())
        {
            if (hist_u_set.find(hist_v[i].first) != hist_u_set.end()) {
                int h = post[hist_v[i].first];
                vec_seg[hist_v[i].first].add(min(h, hist_v[i].second), max(h, hist_v[i].second) + 1, x);
                pivot = hist_v[i].first;
                break;
            }
        }

        rep(i, hist_u.size())
        {
            if (hist_u[i].first == pivot)
                break;
            vec_seg[hist_u[i].first].add(0, hist_u[i].second + 1, x);
        }
        rep(i, hist_v.size())
        {
            if (hist_v[i].first == pivot)
                break;
            vec_seg[hist_v[i].first].add(0, hist_v[i].second + 1, x);
        }
    }
    T query(int u, int v)
    {
        if (!builded) {
            build();
            builded = true;
        }
        vector<pair<int, int>> hist_u;
        vector<pair<int, int>> hist_v;
        rep(j, 2)
        {
            int tmp = j == 1 ? u : v;
            while (true) {
                int cur_col = pos[tmp].first;
                if (j)
                    hist_u.push_back(pos[tmp]);
                else
                    hist_v.push_back(pos[tmp]);
                if (cur_col == 0)
                    break;
                tmp = dict[par[cur_col]];
            }
        }
        int pivot = 0;
        T ans = unit;
        set<int> hist_u_set;
        map<int, int> post;
        for (auto s : hist_u) {
            hist_u_set.insert(s.first);
            post[s.first] = s.second;
        }
        rep(i, hist_v.size())
        {
            if (hist_u_set.find(hist_v[i].first) != hist_u_set.end()) {
                int h = post[hist_v[i].first];
                ans = f(vec_seg[hist_v[i].first].query(min(h, hist_v[i].second), max(h, hist_v[i].second) + 1), ans);
                pivot = hist_v[i].first;
                break;
            }
        }

        rep(i, hist_u.size())
        {
            if (hist_u[i].first == pivot)
                break;
            ans = f(vec_seg[hist_u[i].first].query(0, hist_u[i].second + 1), ans);
        }
        rep(i, hist_v.size())
        {
            if (hist_v[i].first == pivot)
                break;
            ans = f(vec_seg[hist_v[i].first].query(0, hist_v[i].second + 1), ans);
        }
        return ans;
    }
};

int main()
{
    int n, m;
    cin >> n;
    vector<lli> v(n, 0);
    hldec tr(n, v);
    rep(i, n - 1)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        tr.add(u, v);
    }

    int q;
    tr.build(true);

    cin >> q;
    lli sum = 0;
    rep(i, q)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        tr.add(u, v, 1);
        sum += tr.query(u, v);
    }
    cout << sum << endl;

    // //cout << tr.query(0,1)<<endl;
    // cout << tr.query(3, 4) << endl;
};
;
0