Submission #398531

#	Time	Username	Problem	Language	Result	Execution time	Memory
398531		model_code	Arboras (RMI20_arboras)	C++17	100 / 100	342 ms	24964 KiB

arboras

/**
* user:  loginov-0a5
* fname: Igor
* lname: Loginov
* task:  Arboras
* score: 100.0
* date:  2020-12-04 12:01:41.831192
*/
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MOD = 1e9 + 7;
const int N = 101000;

int n;

int et[N], T;

vector<vector<pair<int, long long> > > g;

void dfs0(int v)
{
    et[v] = T++;
    for (auto u : g[v]) dfs0(u.first);
}

int p[N];
long long len[N];
int id[N];

long long d2[N];

int children[N]; // next vertex in the path
int path_id[N]; // where vertex V is located (probably, HLD is needed)
vector<int> path_root; // root of each path
int depth[N]; // distance from root to V in edges
//long long h[N]; // distance from root to V in metres (segment tree)
long long cur1, cur2; // current answers
long long go[N]; // longest path from V in metres, path_root[path_id[V]] == V must holds

long long tree1[4 * N];
long long push1[4 * N];

void Push1(int V)
{
	push1[2 * V + 1] += push1[V];
	push1[2 * V + 2] += push1[V];
	tree1[2 * V + 1] += push1[V];
	tree1[2 * V + 2] += push1[V];
	push1[V] = 0;
}

long long geth(int pos, int L = 0, int R = N, int V = 0)
{
	if (L + 1 == R)
	{
        return tree1[V];
	}
	Push1(V);
	int M = (L + R) / 2;
	if (pos < M) return geth(pos, L, M, 2 * V + 1);
	else return geth(pos, M, R, 2 * V + 2);
}

void addh(int l, int r, long long x, int L = 0, int R = N, int V = 0)
{
	if (R <= l || r <= L) return;
	if (l <= L && R <= r)
	{
		push1[V] += x;
		tree1[V] += x;
		return;
	}
	int M = (L + R) / 2;
	Push1(V);
	addh(l, r, x, L, M, 2 * V + 1);
	addh(l, r, x, M, R, 2 * V + 2);
}

int lst[N];

void dfs(int v, int D, long long H)
{
	depth[v] = D;
	addh(v, v + 1, H);
	long long fnd = 0, fnd2 = 0;
	int mxid = -1;
	lst[v] = v;
	for (auto id : g[v])
	{
		int u = id.first;
		long long w = id.second;
		dfs(u, D + 1, H + w);
		lst[v] = lst[u];
		if (mxid == -1 || go[u] + w > fnd)
        {
            mxid = u;
            fnd2 = fnd;
            fnd = go[u] + w;
        }
        else if (go[u] + w > fnd2)
        {
            fnd2 = go[u] + w;
        }
	}
	d2[v] = fnd2;
	cur2 = (cur2 + fnd2) % MOD;
	//cout << v << " " << mxid << endl;
	if (mxid == -1)
	{
		path_id[v] = path_root.size();
		path_root.push_back(v);
	}
	else
	{
		children[v] = mxid;
		go[v] = go[mxid] + len[mxid];
		path_id[v] = path_id[mxid];
		path_root[path_id[mxid]] = v;
	}
	cur1 = (cur1 + go[v]) % MOD;
}

int get_root(int v)
{
	return path_root[path_id[v]];
}

long long get_actual(int v) // returns correct value of go[v]
{
	int P = get_root(v);
	long long dist = geth(v) - geth(P);
	return go[P] - dist;
}

void update(int v, long long length, int direction)
{
    //cout << v << " " << length << " " << direction << endl;
	if (path_id[direction] == path_id[v])
	{
		long long delta = length - get_actual(v);
		long long P = get_root(v);
		cur1 = (cur1 + (depth[v] - depth[P] + 1) * delta) % MOD;
		go[P] += delta;
		if (P != 0)
		{
			update(p[P], get_actual(P) + len[P], P);
		}
	}
	else
	{
		long long we = get_actual(v);
		if (we >= length)
		{
		    if (length >= d2[v])
		    {
		        cur2 = (cur2 - d2[v] + length) % MOD;
                d2[v] = length;
		    }
		    return;
		}
		int P = get_root(v);
		cur2 = (cur2 - d2[v] + we) % MOD;
		d2[v] = we;
		int nid = path_id[direction];
		go[children[v]] = get_actual(children[v]);
		path_root[path_id[children[v]]] = children[v];
		children[v] = direction;
		//cout << children[v] << " " << direction << " " << get_root(v) << " " << P << endl;
		{
			int kek = v;
			while (1)
            {
                path_id[kek] = nid;
                if (kek == P) break;
                kek = p[kek];
            }
            path_root[path_id[kek]] = kek;
		}
		long long delta = length - we;
		cur1 = (cur1 + (depth[v] - depth[P] + 1) * delta) % MOD;
		go[P] += delta;
		if (P != 0)
		{
			update(p[P], get_actual(P) + len[P], P);
		}
	}
}

void ans()
{
    long long A = cur1;
    for (int i = 0; i < n; i++)
    {
        long long mx1 = 0, mx2 = 0;
        for (auto id : g[i])
        {
            long long Len = get_actual(id.first) + len[id.first];
            if (Len > mx1)
            {
                mx2 = mx1;
                mx1 = Len;
            }
            else if (Len > mx2)
            {
                mx2 = Len;
            }
        }
        A = (A + mx2) % MOD;
    }
    cout << A << "\n";
}

/*
5
0 0 1 1
0 0 0 0
10
1 2
2 2
3 2
4 2
4 1
3 1
2 1
1 1
4 1000
2 1000

7
0 1 1 3 3 4
100000000 100000000 100000000 100000000 100000000 100000000
10
5 1
4 3
6 5
1 1
3 10000000
5 1000000
3 4
1 100000000
4 1000000000
6 100000

7
0 1 1 3 3 4
10 10 10 10 10 10
6
5 1
4 1
6 1
1 1
3 100
5 100

8
0 0 2 0 2 4 3
0
*/

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	g = vector<vector<pair<int, long long> > >(n);
	for (int i = 1; i < n; i++)
	{
		cin >> p[i];
		g[p[i]].push_back({i, 0});
	}
    dfs0(0);
    vector<int> zz(n);
    for (int i = 1; i < n; i++)
    {
        zz[i] = p[i];
    }
    for (int i = 1; i < n; i++)
    {
        p[et[i]] = et[zz[i]];
    }
    for (int i = 1; i < n; i++)
    {
        cin >> zz[i];
        //zz[i] = 100000000 - i;
    }
    for (int i = 1; i < n; i++)
    {
        len[et[i]] = zz[i];
    }
	g = vector<vector<pair<int, long long> > >(n);
	for (int i = 1; i < n; i++)
	{
		id[i] = g[p[i]].size();
		g[p[i]].push_back({i, len[i]});
	}
	dfs(0, 0, 0);

	/*
	for (int i = 0; i < n; i++)
	{
	    cout << get_actual(i) << " ";
	}

	cout << cur1 << "\n";
	//*/

	cout << (cur1 + cur2) % MOD << "\n";

	int q;
	cin >> q;
	while (q--)
	{
		int v, add;
		cin >> v >> add;
		//v = rand() % n;
		//add = 1;

		v = et[v];
		g[p[v]][id[v]].second += add;

		long long g = get_actual(v);

		len[v] += add;

		//cout << v << " " << lst[v] << "\n";
		addh(v, lst[v] + 1, add);

		update(p[v], g + len[v], v);

		/*
        for (int j = 0; j < n; j++)
        {
            cout << path_id[j] << " ";
        }
        cout << "\n";
        for (int j = 0; j < path_root.size(); j++)
        {
            cout << path_root[j] << " ";
        }
        cout << "\n";
        for (int j = 0; j < n; j++)
        {
            cout << go[j] << " ";
        }
        cout << "\n";
        for (int j = 0; j < n; j++)
        {
            cout << geth(j) << " ";
        }
        cout << "\n";
        //*/
        /*
		for (int j = 0; j < n; j++)
		{
		    cout << get_actual(j) << " ";
		}

		cout << "\n";

		cout << cur1 << "\n";
		//*/
		cout << (cur1 + cur2) % MOD << "\n";
		//ans();
	}
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 31 / 31
• Subtask 4: 45 / 45