PROBLEM LINK:
Author: Ritik Mittal
Tester: Nitin Gupta, Lavish Gupta, Takuki Kurokawa
DIFFICULTY:
Medium
PREREQUISITES:
Tree, Square Root Decomposition
PROBLEM:
Given a rooted tree of size N. And each node has some value assigned to it, perform the queries of the following type :
-
1 x y :
- Break the edge between node x and par_x in the tree. It is guaranteed that the node x will be a leaf node of the tree. And make a new tree with par_x be node y. Now make this new tree the original tree, and further operations will be done on this tree.
-
2 x v :
- Change the value on the node x to v.
-
3 x y :
- Calculate the sum of values on each node in the path from node x to node y.
QUICK EXPLANATION:
It is done using query square-root decomposition. After every sqrt(N) queries, the tree is rebuilt. We also maintain a data structure to easily get path sum from u to v. So that for any path sum can be calculated in O(sqrt(N)).
EXPLANATION:
According to the question, we need to maintain a data strucure to get path from u to v. Here we are maintaining a segment tree on eular tour, i.e on entering a node we push +val and on exiting we push -val in tour.
And we are also maintaing a up[node][j] array, that stores ancestor of node that is 2^j level up, and a array level[node] that stores level of all nodes in tree. That is used to calculate lca via binary lifting.
We also maintain array a[node] storing current value of node.
We will recalculate the tree and this eular tour and tin, tout values of nodes in tree after every sqrt(N) queries.
Initially we make a tree and build up array.
- For queries of type 1 :
To break the node x and append it to some other node y, we just mark the node as updated, and store it in some array that will be latter used to unmark the node. And then we also update the up array for node x with up[x][0] = y. We also update level of the node as level[x] = level[y] + 1. - For queries of type 2 :
We just update the value for node in segment tree at tin[node] and tout[node] and we also update a[node]. - For queries of type 3 :
We first calculate lca of nodes u and v.
We go up the tree from node u untill we reach unmarked node or at lca and we do similar for node v. And maintain a sum S. Let us we reach at node P_u from u and P_v from v. Then we calculate sum X on path from P_u to P_v using our segment tree. The answer to the query will be S+X.
Time Complexity Analysis : Let us assume we rebuild the tree after every B queries, We can see that time required for type_1 and for type_2 query is O(log(n)), and for type_3 query, we need to check all the marked nodes one by one, that are also ancestors of the nodes u and v and then from the reached nodes, we calculate further sum in O(log(n)).
So every query contribute log(n) factor and type_3 query contribute additional O(B) factor. If we consider the queries of each type occur with equal probability and we rebuild the tree after every B queries the time complexity is given by :
(Q*log(N)) + ((Q/B) * N) + (Q*B))
One can simply say the optimal choice of B here will be sqrt(N). giving a final time complexity of O(Q*sqrt(N)).
Bonus : Note that here if we rebuild after every B queries, we don’t necessarily have B marked nodes, and during execution of type_3 query, among these marked nodes, we only go through the nodes that are ancestors as well , that further decreases the number of nodes we have iterate over. In general case that is a pretty significant number. So the optimal choice for B is much higher than the sqrt(N), as calculated above.
Note : We can avoid the segment tree and rather use a prefix function on tree and by keeping track on updated nodes and check if it lies on path, This will further reduce the time complexity.
SOLUTIONS:
Setter’s Solution
#include <bits/stdc++.h>
#define int long long int
#define double long double
#define endl '\n'
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define eb emplace_back
#define tr(k,st,en) for(int k = st; k <= en ; k++)
#define trb(k,en,st) for(int k = en; k >= st ; k--)
#define test int TN; cin>>TN; tr(T,1,TN)
#define mxe(c) max_element(all(c))
#define mne(c) min_element(all(c))
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template < typename T_container, typename T = typename enable_if < !is_same<T_container, string>::value, typename T_container::value_type >::type > ostream & operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
typedef pair<int, int> pr;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pr> vpr;
//const int mod = 1e9+7;
//const int inf = 9e18;
class SegTree {
int n; int bs;
vi Tree;
public:
SegTree (int _n) {
n = _n;
bs = 1;
while (bs < n) {
bs *= 2;
}
Tree.assign(2 * bs, 0);
}
void build(vi & ar) {
tr(i, 0, n - 1) Tree[bs + i] = ar[i];
trb(i, bs - 1, 1) {
Tree[i] = Tree[2 * i] + Tree[2 * i + 1];
}
}
void update(int idx, int v) {
idx += bs;
Tree[idx] = v;
while (idx > 1) {
Tree[idx / 2] = Tree[idx] + Tree[idx ^ 1];
idx /= 2;
}
}
int query(int l, int r) {
r++;
l += bs; r += bs;
int ret = 0;
for (; l < r; l /= 2, r /= 2) {
if (l & 1) ret = ret + Tree[l++];
if (r & 1) ret = ret + Tree[--r];
}
return ret;
}
};
int n;
vector<vector<int>> G;
vi a;
vi tin, tout, arr, lvl;
int tme;
void dfs(int x, int p) {
arr[tme] = a[x];
tin[x] = tme++;
for (int nb : G[x]) {
dfs(nb, x);
}
arr[tme] = -a[x];
tout[x] = tme++;
}
int MX = 17;
vvi up;
void pre(int x, int p, int lv = 0) {
up[x][0] = p;
lvl[x] = lv;
tr(i, 1, MX) up[x][i] = up[up[x][i - 1]][i - 1];
for (int nb : G[x]) {
pre(nb, x, lv + 1);
}
}
int lca(int u, int v) {
if (lvl[v] > lvl[u]) swap(v, u);
int to = lvl[u] - lvl[v];
int nu = u, nv = v;
trb(i, MX, 0) {
if (to & (1 << i)) {
nu = up[nu][i];
}
}
if (nu == nv) {
return nu;
}
trb(i, MX, 0) {
if (up[nu][i] != up[nv][i]) {
nu = up[nu][i];
nv = up[nv][i];
}
}
return up[nv][0];
}
void gen_grap() {
G.assign(n + 1, vector<int>());
tr(i, 2, n) {
int p = up[i][0];
G[p].eb(i);
}
dfs(1, 0);
}
void solve() {
cin >> n;
a.assign(n + 1, 0);
tin.assign(n + 1, 0);
tout.assign(n + 1, 0);
arr.assign(2 * n, 0);
lvl.assign(n + 1, 0);
up.assign(n + 1, vi(MX + 1));
tr(i, 2, n) {
int p; cin >> p;
up[i][0] = p;
}
tr(i, 1, n) cin >> a[i];
int q; cin >> q;
int B = sqrt(n * log2(n));
SegTree seg(2 * n);
tme = 0;
gen_grap();
pre(1, 0);
seg.build(arr);
vi to_p;
vi is_marked(n + 1, 0);
tr(i, 0, q - 1) {
if (i % B == 0 and i != 0) {
tme = 0;
gen_grap();
seg.build(arr);
for (int x : to_p) is_marked[x] = 0;
to_p.clear();
}
int t; cin >> t;
if (t == 1) {
int x, p; cin >> x >> p;
up[x][0] = p;
tr(i, 1, MX) up[x][i] = up[up[x][i - 1]][i - 1];
lvl[x] = lvl[p] + 1;
is_marked[x] = 1;
to_p.eb(x);
} else if (t == 2) {
int x, val; cin >> x >> val;
a[x] = val;
seg.update(tin[x], val);
seg.update(tout[x], -val);
} else {
int u, v;
cin >> u >> v;
int lc = lca(u, v);
int ret = 0;
while (is_marked[u] and u != lc) {
ret += a[u];
u = up[u][0];
}
while (is_marked[v] and v != lc) {
ret += a[v];
v = up[v][0];
}
if (u == v) {
ret += a[v];
cout << ret << endl;
} else {
ret += seg.query(tin[lc], tin[v]);
ret += seg.query(tin[lc], tin[u]);
ret -= a[lc];
cout << ret << endl;
}
}
}
}
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
solve();
return 0;
}
// 1) x, new_par[x]
// 2) y, new_val[y]
// 3) u, v -> get_sum
Tester's (Lavish Gupta) Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 10;
const int MAX_N = 100000;
const int MAX_Q = 100000;
const int MAX_val = 1000000000;
const int MAX_SUM_N = 100000;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll z = 1000000007;
ll sum_nk = 0 ;
int par[MAX_N][20] ;
ll tree[8*MAX_N] ;
int is_marked[MAX_N] ;
int level[MAX_N] ;
vector<int> adj[MAX_N] ;
ll val[MAX_N] ;
ll tot_val[2 * MAX_N] ;
int tin[MAX_N] ;
int tout[MAX_N] ;
ll path_length = 0 ;
ll marked_count = 0 ;
int ti = 0 ;
ll left(ll i){return ((2*i)+1) ;}
ll right(ll i){return ((2*i) + 2) ;}
void build_Tree(ll arr[] , ll par , ll l, ll r)
{
if(l == r)
{
tree[par] = arr[r] ;
return ;
}
ll mid = (l+r)/2 ;
build_Tree(arr , (2*par)+1 , l , mid) ;
build_Tree(arr , (2*par)+2 , mid+1 , r) ;
tree[par] = tree[(2*par)+1] + tree[(2*par)+2] ;
return ;
}
void update(ll par , ll l , ll r , ll ind , ll val)
{
if(l == r && l == ind)
{
tree[par] = val ;
return ;
}
ll mid = (l+r)/2 ;
if(ind <= mid)
update((2*par)+1 , l , mid , ind , val) ;
else
update((2*par)+2 , mid+1 , r , ind , val) ;
tree[par] = tree[(2*par)+1] + tree[(2*par)+2] ;
}
ll query(ll par , ll l , ll r , ll l_ind , ll r_ind) // update type and what to return in extreme case
{
if(l_ind > r || r_ind < l)
return 0;
if(l_ind <= l && r_ind >= r)
{
return tree[par] ;
}
ll mid = (l+r)/2 ;
ll a = query((2*par)+1 , l , mid , l_ind , r_ind) ;
ll b = query((2*par)+2 , mid+1, r , l_ind , r_ind) ;
ll c = a+b ;
return c ;
}
void dfs(int u , int p)
{
tin[u] = ti++ ;
tot_val[tin[u]] = val[u] ;
par[u][0] = p ;
if(u == 0)
level[u] = 0 ;
else
level[u] = level[p]+1 ;
for(int i = 1 ; i < 20 ; i++)
par[u][i] = par[par[u][i-1]][i-1] ;
for(int i = 0 ; i < adj[u].size() ; i++)
{
int v = adj[u][i] ;
if(v != p)
dfs(v , u) ;
}
tout[u] = ti++ ;
tot_val[tout[u]] = -val[u] ;
return ;
}
void get_adj(int n)
{
for(int i = 0 ; i < n ; i++)
{
level[i] = 0 ;
is_marked[i] = 0 ;
adj[i].clear() ;
}
for(int i = 1 ; i < n ; i++)
{
adj[i].push_back(par[i][0]) ;
adj[par[i][0]].push_back(i) ;
}
return ;
}
bool is_ancestor(int x , int y)
{
if(tin[x] < tin[y])
if(tout[x] > tout[y])
return true ;
return false ;
}
int get_lca(int x , int y)
{
if(level[x] < level[y])
swap(x , y) ;
int to = level[x] - level[y] ;
//cout << "to = " << to << endl ;
for(int i = 0 ; i < 20 ; i++)
{
if(((1 << i) & to) != 0)
{
path_length += ((1 << i)) ;
x = par[x][i] ;
}
}
if(x == y)
return x ;
for(int i = 19 ; i >= 0 ; i--)
{
if(par[x][i] != par[y][i])
{
x = par[x][i] ;
y = par[y][i] ;
path_length += ((1 << (i+1))) ;
}
}
path_length += 2 ;
return par[x][0] ;
}
void solve()
{
int n;
cin >> n ;
for(int i = 1 ; i < n ; i++)
{
int p;
cin >> p ;
p-- ;
par[i][0] = p ;
adj[i].push_back(p) ;
adj[p].push_back(i) ;
}
par[0][0] = 0 ;
for(int i = 0 ; i < n ; i++)
{
cin >> val[i] ;
}
ll type[3] = {0 , 0 , 0} ;
int q ;
cin >> q ;
int qquery[q][3] ;
for(int i = 0 ; i < q ; i++)
{
int x , y , t;
cin >> t ;
type[t-1]++ ;
cin >> x ;
cin >> y ;
x-- ;
if(t != 2)
y-- ;
qquery[i][0] = t ;
qquery[i][1] = x ;
qquery[i][2] = y ;
}
for(int i = 0 ; i < 3 ; i++)
{
cerr << "Queries of type " << i+1 << " = " << type[i] << endl ;
}
/********************************** Input Verified **************************************/
int seg = 3 * sqrtl(q) ;
for(int i = 0 ; i < q ; i++)
{
int t = qquery[i][0] , x = qquery[i][1] , y = qquery[i][2] ;
if(i%seg == 0)
{
ti = 0 ;
get_adj(n) ;
dfs(0 , 0) ;
build_Tree(tot_val , 0 , 0 , 2*n-1) ;
}
if(t == 1)
{
par[x][0] = y ;
level[x] = level[y]+1 ;
is_marked[x] = 1 ;
for(int j = 1 ; j < 20 ; j++)
par[x][j] = par[par[x][j-1]][j-1] ;
}
if(t == 2)
{
val[x] = y ;
update(0 , 0 , 2*n - 1 , tin[x] , y) ;
update(0 , 0 , 2*n - 1 , tout[x] , -y) ;
}
if(t == 3)
{
ll ans = 0 ;
int l = get_lca(x , y) ;
while(x != l && is_marked[x] == 1)
{
marked_count++ ;
ans += val[x] ;
x = par[x][0] ;
}
while(y != l && is_marked[y] == 1)
{
marked_count++ ;
ans += val[y] ;
y = par[y][0] ;
}
if(x == y && x == l)
{
ans += val[x] ;
cout << ans << '\n' ;
continue ;
}
ans += query(0 , 0 , 2*n-1 , tin[l] , tin[x]);
ans += query(0 , 0 , 2*n-1 , tin[l] , tin[y]);
ans -= val[l] ;
cout << ans << '\n' ;
}
}
cerr << "Total Path length = " << path_length << endl ;
cerr << "Total Marked Count = " << marked_count << endl ;
return ;
}
signed main()
{
fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int t = 1;
// t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve() ;
}
// assert(getchar() == -1);
// assert(sum_n <= MAX_SUM_N);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"Sum of lengths : " << sum_n << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr << "Sum of product : " << sum_nk << '\n' ;
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Tester's (Takuki Kurokawa) Solution
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
template <typename T>
struct fenwick {
int n;
vector<T> node;
fenwick(int _n) : n(_n) {
node.resize(n);
}
void add(int x, T v) {
while (x < n) {
node[x] += v;
x |= (x + 1);
}
}
T get(int x) { // [0, x]
T v = 0;
while (x >= 0) {
v += node[x];
x = (x & (x + 1)) - 1;
}
return v;
}
T get(int x, int y) { // [x, y]
return (get(y) - (x ? get(x - 1) : 0));
}
int lower_bound(T v) {
int x = 0;
int h = 1;
while (n >= (h << 1)) {
h <<= 1;
}
for (int k = h; k > 0; k >>= 1) {
if (x + k <= n && node[x + k - 1] < v) {
v -= node[x + k - 1];
x += k;
}
}
return x;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
const int m = (int) 2e5 + 10;
vector<vector<int>> p(20, vector<int>(m + 1, m));
for (int i = 1; i < n; i++) {
cin >> p[0][i];
p[0][i]--;
}
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> b(m);
iota(b.begin(), b.end(), 0);
int q;
cin >> q;
vector<tuple<int, int, int>> que(q);
for (int i = 0; i < q; i++) {
int op, x, y;
cin >> op >> x >> y;
x--;
y -= op % 2;
que[i] = make_tuple(op, x, y);
}
vector<vector<int>> vs(n);
for (int i = 0; i < n; i++) {
vs[i].emplace_back(i);
}
for (int i = 0; i < q; i++) {
auto [op, x, y] = que[i];
if (op == 1) {
vs[x].emplace_back(n);
p[0][n] = vs[y].back();
b[n] = x;
n++;
}
}
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
g[p[0][i]].emplace_back(i);
for (int j = 1; j < 20; j++) {
p[j][i] = p[j - 1][p[j - 1][i]];
}
}
vector<int> order, beg(n), end(n), depth(n);
function<void(int)> dfs = [&](int v) {
beg[v] = (int) order.size();
order.emplace_back(v);
for (int to : g[v]) {
depth[to] = depth[v] + 1;
dfs(to);
}
end[v] = (int) order.size();
};
dfs(0);
auto anc = [&](int x, int y) {
return (beg[x] <= beg[y] && end[y] <= end[x]);
};
auto lca = [&](int x, int y) {
if (anc(x, y)) {
return x;
}
if (anc(y, x)) {
return y;
}
for (int j = 19; j >= 0; j--) {
if (p[j][x] != m && !anc(p[j][x], y)) {
x = p[j][x];
}
}
return p[0][x];
};
fenwick<long long> f(m);
for (int i = 0; i < (int) a.size(); i++) {
f.add(beg[i], a[i]);
f.add(end[i], -a[i]);
}
vector<int> idx(n);
for (int i = 0; i < q; i++) {
auto [op, x, y] = que[i];
if (op == 1) {
int now = vs[x][idx[x]];
f.add(beg[now], -a[x]);
f.add(end[now], a[x]);
idx[x]++;
now = vs[x][idx[x]];
f.add(beg[now], a[x]);
f.add(end[now], -a[x]);
} else if (op == 2) {
int now = vs[x][idx[x]];
f.add(beg[now], -a[x]);
f.add(end[now], a[x]);
a[x] = y;
f.add(beg[now], a[x]);
f.add(end[now], -a[x]);
} else {
x = vs[x][idx[x]];
y = vs[y][idx[y]];
int z = lca(x, y);
long long ans = f.get(beg[x]) + f.get(beg[y]) - f.get(beg[z]) * 2 + a[b[z]];
if (a[b[z]] != f.get(beg[z], beg[z])) {
cerr << z << " " << a[b[z]] << " " << f.get(beg[z], beg[z]) << " " << b[z] << " " << beg[z] << endl;
}
cout << ans << '\n';
}
}
return 0;
}