답안 #646516

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646516 2022-09-29T23:14:51 Z danikoynov Arboras (RMI20_arboras) C++14
100 / 100
4849 ms 34480 KB
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

int n, q;
int heavy[maxn], ch_idx[maxn], ch_pos[maxn], ch_head[maxn];
int par[maxn], depth[maxn], sub[maxn], strong[maxn];
ll dp[maxn][2], dis[maxn];
vector < pair < int, ll > > g[maxn];

void dfs(int v)
{
    heavy[v] = -1;
    strong[v] = -1;
    for (pair < int, ll > nb : g[v])
    {
        if (nb.first == par[v])
            continue;

        depth[nb.first] = depth[v] + 1;
        dfs(nb.first);
        if (heavy[v] == -1 || sub[nb.first] > sub[heavy[v]])
            heavy[v] = nb.first;
        if (dp[nb.first][0] + nb.second >= dp[v][0])
        {
            dp[v][1] = dp[v][0];
            dp[v][0] = dp[nb.first][0] + nb.second;
            strong[v] = nb.first;
        }
        else if (dp[nb.first][0] + nb.second > dp[v][1])
        {
            dp[v][1] = dp[nb.first][0] + nb.second;
        }
    }
}

const int block = 10;
ll ans = 0;
pair < ll, ll > tree[4 * maxn];
ll lazy[4 * maxn], nxt_free, pot[maxn];
struct chain
{
    vector < int > ver;
    vector < pair < ll, ll > > st;
    set < int > weak;
    int ch_root;


    void build_tree(int root, int left, int right)
    {
        if (left == right)
        {
            pot[ver[left]] = ch_root + root;
            tree[ch_root + root] = st[left];
            return;
        }

        int mid = (left + right) / 2;
        build_tree(root * 2, left, mid);
        build_tree(root * 2 + 1, mid + 1, right);

    }


    void build_chain()
    {
        for (int i = 0; i < ver.size(); i ++)
        {
            st.push_back({dp[ver[i]][0], dp[ver[i]][1]});
            if (i != (int)(ver.size()) - 1)
            {
                if (strong[ver[i]] != ver[i + 1])
                    weak.insert(i);
            }
        }
        ch_root = nxt_free;
        nxt_free += ver.size() * 4;
        build_tree(1, 0, (int)st.size() - 1);
    }

    void push_lazy(int root, int left, int right)
    {
        ///if (lazy[root].first == lazy[root].second && lazy[root].first == 0)
        if (left == right)
        {
            tree[root + ch_root].first += lazy[ch_root + root];
        }
        else
        {
            lazy[ch_root + root * 2] += lazy[ch_root + root];
            lazy[ch_root + root * 2 + 1] += lazy[ch_root + root];
        }
        lazy[ch_root + root] = 0;
    }

    pair < ll, ll > get_node(int root, int left, int right, int idx)
    {
        int mid;
        while(true)
        {
            if (lazy[ch_root + root] != 0)
                push_lazy(root, left, right);
            if (left == right)
            {
                return tree[ch_root + root];
            }
            mid = (left + right) / 2;
            if (idx <= mid)
            {
                root = root * 2;
                right = mid;
            }
            else
            {
                root = root * 2 + 1;
                left = mid + 1;
            }
        }
        /**if (lazy[ch_root + root] != 0)
            push_lazy(root, left, right);
        if (left == right)
            return tree[ch_root + root];

        int mid = (left + right) / 2;
        if (idx <= mid)
            return get_node(root * 2, left, mid, idx);
        return get_node(root * 2 + 1, mid + 1, right, idx);*/
    }

    void set_node(int root, int left, int right, int idx, pair < ll,ll >  val)
    {
        int mid;
        while(true)
        {
            if (lazy[ch_root + root] != 0)
                push_lazy(root, left, right);
            if (left == right)
            {
                tree[ch_root + root] = val;
                return;
            }
                    mid = (left + right) / 2;
            if (idx <= mid)
            {
                root = root * 2;
                right = mid;
            }
            else
            {
                root = root * 2 + 1;
                left = mid + 1;
            }
        }
        /**if (lazy[ch_root + root] != 0)
            push_lazy(root, left, right);
        if (left == right)
        {
            tree[ch_root + root] = val;
            return;
        }

        int mid = (left + right) / 2;
        if (idx <= mid)
            set_node(root * 2, left, mid, idx, val);
        else
            set_node(root * 2 + 1, mid + 1, right, idx, val);*/

    }

    struct sol
    {
        int root, left, right, qleft, qright;
        ll val;

        sol(int _root, int _left, int _right, int _qleft, int _qright, ll _val)
        {
            root = _root;
            left = _left;
            right = _right;
            qleft = _qleft;
            qright = _qright;
            val = _val;
        }
    };
   void update_range(int root, int left, int right, int qleft, int qright, ll val)
    {
        if (lazy[ch_root + root] != 0)
            push_lazy(root, left, right);

        if (left == qleft && right == qright)
        {
            lazy[ch_root + root] = val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        if (qright <= mid)
            update_range(root * 2, left, mid, qleft, qright, val);
        else if (qleft > mid)
            update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
        else
        {
            update_range(root * 2, left, mid, qleft, mid, val);
            update_range(root * 2 + 1, mid + 1, right, mid + 1, qright, val);
        }
        /**if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root + ch_root] = val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;

        update_range(root * 2, left, mid, qleft, qright, val);
        update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);*/
    }
    pair < ll, ll > get_element(int v)
    {
        if (ver.size() < block)
        return {dp[v][0], dp[v][1]};
        return get_node(1, 0, (int)(ver.size()) - 1, ch_pos[v]);
    }

    void set_element(int v, pair < ll, ll > val)
    {
        if (ver.size() < block)
        {
            dp[v][0] = val.first;
            dp[v][1] = val.second;
            return;
        }
        set_node(1, 0, (int)(ver.size()) - 1, ch_pos[v], val);
    }

    void update_path(int lf, int rf, ll val)
    {
        if (ver.size() < block)
        {
            for (int i = lf; i <= rf; i ++)
                dp[ver[i]][0] += val;
        }
        update_range(1, 0, (int)(ver.size()) - 1, lf, rf, val);
    }

};

vector < chain > ch;

void hld(int v)
{
    ch_pos[v] = ch.back().ver.size();
    ch.back().ver.push_back(v);
    ch_head[v] = ch.back().ver[0];
    ch_idx[v] = (int)(ch.size()) - 1;


    if (heavy[v] != -1)
    {
        hld(heavy[v]);
    }

    for (pair < int, ll > nb : g[v])
    {
        if (nb.first == par[v] || nb.first == heavy[v])
            continue;
        ch.emplace_back();
        hld(nb.first);

    }
}

void update(int v, ll d)
{
    ll cur = dp[v][0];
    dis[v] += d;
    while(true)
    {
        if (v == 0)
            break;
        cur = cur + dis[v];
        ///cout << v << " :: " << cur << endl;
        if (strong[par[v]] == v)
        {
            ans = ans + cur - dp[par[v]][0];
            ans = (ans + mod) % mod;
            dp[par[v]][0] = cur;
            v = par[v];
            continue;
        }

        if (cur <= dp[par[v]][1])
            break;
        if (cur <= dp[par[v]][0])
        {
            ans = ans + cur - dp[par[v]][1];
            ans = (ans + mod) % mod;
            dp[par[v]][1] = cur;
            break;
        }
        ans = ans + cur - dp[par[v]][1];
        ans = (ans + mod) % mod;
        dp[par[v]][1] = dp[par[v]][0];
        dp[par[v]][0] = cur;
        strong[par[v]] = v;
        v = par[v];
    }

    /**cout << "------------" << endl;
    for (int i = 0; i < n; i ++)
        cout << dp[i][0] << " " << dp[i][1] << endl;
    cout << "------------" << endl;*/
}

void update_edge(int v, ll d)
{
    dis[v] += d;
    pair < ll, ll > cur, aft;
    set < int > :: iterator it;
    cur = ch[ch_idx[v]].get_element(v);
    while(true)
    {
        ///cout << "here " << v << endl;
        if (v == 0)
            break;
        if (ch_head[v] == v)
        {
            ///cur = ch[ch_idx[v]].get_element(v);
            aft = ch[ch_idx[par[v]]].get_element(par[v]);
            if (strong[par[v]] == v)
            {
                ans = (ans + cur.first + dis[v] - aft.first) % mod;
                aft.first = cur.first + dis[v];
                ch[ch_idx[par[v]]].set_element(par[v], aft);
                v = par[v];
                cur = aft;
            }
            else
            {

                if (cur.first + dis[v] <= aft.second)
                    break;
                if (cur.first + dis[v] <= aft.first)
                {
                    ans = (ans + cur.first + dis[v] - aft.second) % mod;
                    aft.second = cur.first + dis[v];
                    ch[ch_idx[par[v]]].set_element(par[v], aft);
                    break;
                }

                ans = (ans + cur.first + dis[v] - aft.second) % mod;

                if (strong[par[v]] == ch[ch_idx[par[v]]].ver[ch_pos[par[v]] + 1])
                    ch[ch_idx[par[v]]].weak.insert(ch_pos[par[v]]);
                strong[par[v]] = v;

                aft.second = aft.first;
                aft.first = cur.first + dis[v];
                ch[ch_idx[par[v]]].set_element(par[v], aft);
                v = par[v];
                cur = aft;
                continue;
            }
        }
        else
        {
            int pos = 0;
            if (!ch[ch_idx[v]].weak.empty())
            {
                it = ch[ch_idx[v]].weak.lower_bound(ch_pos[v]);
                if (it != ch[ch_idx[v]].weak.begin())
                {
                    it = prev(it);
                    pos = *it + 1;
                }
            }
            /**for (int x : ch[ch_idx[v]].weak)
                cout << x << " ";
            cout << endl;*/
            ///cout << pos << " " << ch_pos[v] << endl;
            if (pos == ch_pos[v])
            {

                ///cur = ch[ch_idx[v]].get_element(v);
                aft = ch[ch_idx[par[v]]].get_element(par[v]);
                if (cur.first + dis[v] <= aft.second)
                    break;
                if (cur.first + dis[v] <= aft.first)
                {
                    ans = (ans + cur.first + dis[v] - aft.second) % mod;
                    aft.second = cur.first + dis[v];
                    ch[ch_idx[par[v]]].set_element(par[v], aft);
                    break;
                }

                strong[par[v]] = v;
                ch[ch_idx[v]].weak.erase(pos - 1);
                ans = (ans + cur.first + dis[v] - aft.second) % mod;
                aft.second = aft.first;
                aft.first = cur.first + dis[v];
                ch[ch_idx[v]].set_element(par[v], aft);
                v = par[v];
                cur = aft;
                continue;

            }
            else
            {
                ///cur = ch[ch_idx[v]].get_element(v);
                aft = ch[ch_idx[par[v]]].get_element(par[v]);
                ll diff = cur.first + dis[v] - aft.first;
                ans = (ans + diff * (ch_pos[v] - pos)) % mod;
                ch[ch_idx[v]].update_path(pos, ch_pos[v] - 1, diff);
                v = ch[ch_idx[v]].ver[pos];
                cur = ch[ch_idx[v]].get_element(v);
                continue;
            }
        }
    }
}
void solve()
{
    cin >> n;
    for (int i = 1; i < n; i ++)
        cin >> par[i];
    for (int i = 1; i < n; i ++)
    {
        cin >> dis[i];
        g[par[i]].push_back({i, dis[i]});
    }

    par[0] = -1;
    dfs(0);
    ch.emplace_back();
    hld(0);

    /**for (int i = 0; i < ch.size(); i ++)
    {
        cout << i << " : ";
        for (int v : ch[i].ver)
            cout << v << " ";
        cout << endl;
    }*/

    for (int i = 0; i < ch.size(); i ++)
        ch[i].build_chain();

    for (int i = 0; i < ch.size(); i ++)
    {
        for (int j = 0; j < (int)ch[i].ver.size() - 1; j ++)
        {
            if (strong[ch[i].ver[j]] != ch[i].ver[j + 1])
                ch[i].weak.insert(j);
        }
    }

    cin >> q;
    for (int i = 0; i < n; i ++)
        ans = (ans + dp[i][0] + dp[i][1]) % mod;
    cout << ans << endl;
    for (int i = 0; i < q; i ++)
    {
        ///if (i % 10000 == 0)
           // cout << "YEP" << endl;
        int v;
        ll d;
        cin >> v >> d;
        ///update(v, d);
        update_edge(v, d);
        cout << ans << endl;
    }
}

int main()
{
    ///freopen("input.txt", "r", stdin);
    speed();
    solve();
    return 0;
}

Compilation message

arboras.cpp: In member function 'void chain::build_chain()':
arboras.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < ver.size(); i ++)
      |                         ~~^~~~~~~~~~~~
arboras.cpp: In function 'void solve()':
arboras.cpp:469:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<chain>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  469 |     for (int i = 0; i < ch.size(); i ++)
      |                     ~~^~~~~~~~~~~
arboras.cpp:472:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<chain>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  472 |     for (int i = 0; i < ch.size(); i ++)
      |                     ~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 3 ms 3012 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 31220 KB Output is correct
2 Correct 70 ms 32032 KB Output is correct
3 Correct 86 ms 32800 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3832 ms 31072 KB Output is correct
2 Correct 99 ms 29912 KB Output is correct
3 Correct 100 ms 32372 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 3 ms 3012 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 128 ms 31220 KB Output is correct
5 Correct 70 ms 32032 KB Output is correct
6 Correct 86 ms 32800 KB Output is correct
7 Correct 3832 ms 31072 KB Output is correct
8 Correct 99 ms 29912 KB Output is correct
9 Correct 100 ms 32372 KB Output is correct
10 Correct 4849 ms 31128 KB Output is correct
11 Correct 113 ms 31920 KB Output is correct
12 Correct 119 ms 34480 KB Output is correct
13 Correct 87 ms 23872 KB Output is correct
14 Correct 86 ms 23856 KB Output is correct