結果

問題 No.399 動的な領主
コンテスト
ユーザー uenoku
提出日時 2018-01-19 04:16:43
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,175 ms / 2,000 ms
コード長 8,425 bytes
コンパイル時間 3,505 ms
コンパイル使用メモリ 214,672 KB
実行使用メモリ 48,496 KB
最終ジャッジ日時 2024-12-24 09:21:56
合計ジャッジ時間 15,065 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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