PROBLEM LINK:
Author: Sandeep Singh
Tester: Soham Chakrabarti
Editorialist: Sandeep Singh
DIFFICULTY:
MEDIUM
PREREQUISITES:
Euler Tour, Bit/segment Tree
QUICK EXPLANATION:
Find the in time and out time for each node (village) using Euler tour. Take a temp array and store positive value of each node at index = it’s in time and negative value at index = it’s out time. Use Bit or segment tree on temp to answer the queries. For type 1 query, just find range sum on temp from index 0 to out[x]-1. For type 2 query, update index in[x] by +u and out[x] by -u. Keep the value of node 1 zero throughout the queries. Skip all its updates.
EXPLANATION:
The problem is a trivial range query and point update question which can be easily solved using segment tree or Fenwick tree (Bit). We just need to convert the tree into an array and then use Bit or segment tree on it.
We use the Euler Tour technique to store the in time and out time of each node. We will use these values as indexes. In the $temp array, at in value of each node, we will store the positive value of the node at the out time, we store the negative value of the node.
Realize that the answer to the queries is as follows:
For type 1 query, just find range sum on temp from index 0 to out[x]-1. For type 2 query, update index in[x] by +u and out[x] by -u.
The implementation is very trivial. We just have to be careful about node 1. We keep its value 0 throughout the queries and skip all updates on it.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for( i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for( i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define MAX 100005
using namespace std;
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////
ll tax[MAX],temp[2*MAX],in[2*MAX],out[2*MAX];
int t=0;
vector<int>g[MAX];
ll getSum(ll* BITree, int index)
{
ll sum = 0;
index = index + 1;
while (index>0)
{
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
void updateBIT(ll* BITree, int n, int index, ll val)
{
index = index + 1;
while (index <= n)
{
BITree[index] += val;
index += index & (-index);
}
}
ll *constructBITree(int n)
{
ll *BITree = new ll[n+1];
for (int i=1; i<=n; i++)
BITree[i] = 0;
for (int i=0; i<n; i++)
updateBIT(BITree, n, i, temp[i]);
return BITree;
}
void dfs(int u,int parent){
in[u]=t++;
for(int child:g[u]){
if(child!=parent){
dfs(child,u);
}
}
out[u]=t++;
}
void solve(){
ll n,Q,i,j,u,x;
cin>>n>>Q;
for(i=0;i<n-1;i++){
cin>>u>>x;
g[u].push_back(x);
g[x].push_back(u);
}
for(i=1;i<=n;i++)cin>>tax[i];
tax[1]=0;
dfs(1,0);
for(i=1;i<=n;i++){
temp[in[i]]=tax[i];
temp[out[i]]=-(tax[i]);
}
ll *BT=constructBITree(t);
while(Q--){
cin>>i;
if(i==1){
cin>>x;
cout<<getSum(BT,out[x]-1)<<endl;
}
else{
cin>>x>>u;
if(x==1)
continue;
updateBIT(BT,t,in[x],u);
updateBIT(BT,t,out[x],-u);
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("ip6.in","r",stdin);
freopen("op6.out","w",stdout);
#endif
solve();
}
Tester's Solution
/* nuttela - Soham Chakrabarti */
#include <bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
const int N = 1e5+5;
const int inf = INT_MAX;
const ll MOD = 1e9 + 7;
/*typedef struct data
{
data* bit[2];
int val = 0;
} trie;
void insert(int x){
trie* curr = head;
for (int i = 30; i >= 0; --i)
{
int b = x&(1<<i);
if(!curr->bit[b]){
curr->bit[b] = new trie();
}
curr = curr->bit[b];
}
curr->val=x;
}
int minXor(int x){
trie* curr = head;
}*/
vector<ll> G[N];
const ll LG = ceil(log2(N));
vector<vector<ll>> up(N, vector<ll>(LG+1));
vector<ll> lvl(N),order,idx(N),sz(N),T(4*N),lazy(4*N),pre;
int val[N]={0};
void dfs(ll u,ll par){
idx[u] = order.size();
order.pb(u);
sz[u] = 1;
up[u][0] = par;
for(ll i = 1; i <= LG; i++){
up[u][i]=up[up[u][i-1]][i-1];
}
for(auto x : G[u]){
if(x!=par){
dfs(x,u);
sz[u]+=sz[x];
}
}
}
int lca(int v) {
ll res=val[v];
int from = 0;
for(int i = 0;;++i) {
if(up[v][from]!=1) {
if(pre[up[v][from]]!=0){
res+=pre[up[v][from]];
break;
}
res+=val[up[v][from]];
v=up[v][from];
}else break;
}
return res;
}
void build(int node,int s, int e){
if(s==e){
T[node] = pre[order[s]];
return;
}
int m=(s+e)>>1;
build(node<<1,s,m);
build(node<<1|1,m+1,e);
T[node]=(T[node<<1]+T[node<<1|1]);
}
int query(int node, int a, int b, int i, int j) {//1,4,4,4
if(a > b || a > j || b < i) return 0; // Out of range
if(lazy[node] != 0) { // This node needs to be updated
T[node] += lazy[node]; // Update it
if(a != b) {
lazy[node<<1] += lazy[node]; // Mark child as lazy
lazy[node<<1|1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a >= i && b <= j) // Current segment is totally within range [i, j]
return T[node];
int q1 = query(node<<1, a, (a+b)/2, i, j); // Query left child
int q2 = query(node<<1|1, 1+(a+b)/2, b, i, j); // Query right child
int res = (q1 + q2); // Return final result
return res;
}
void upd(int node, int a, int b, int i, int j, int value){
if(lazy[node] != 0) { // This node needs to be updated
T[node] += lazy[node]; // Update it
if(a != b) {
lazy[node<<1] += lazy[node]; // Mark child as lazy
lazy[node<<1|1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a > b || a > j || b < i) // Current segment is not within range [i, j]
return;
if(a >= i && b <= j) { // Segment is fully within range
T[node] += value;
if(a != b) { // Not leaf node
lazy[node<<1] += value;
lazy[node<<1|1] += value;
}
return;
}
upd(node<<1, a, (a+b)/2, i, j, value); // Updating left child
upd(node<<1|1, 1+(a+b)/2, b, i, j, value); // Updating right child
T[node] = (T[node<<1] + T[node<<1|1]); // Updating root with max value
}
int main() {
IO;
//int t;cin>>t;
//while(t--){
ll n,q;cin>>n>>q;
val[0]=0;
for (int i = 1; i < n; ++i)
{
ll u,v;cin>>u>>v;
G[u].pb(v);
G[v].pb(u);
}
for (int i = 0; i < n; ++i)
{
ll x;cin>>x;
val[i+1]=x;
}
dfs(1,1);
pre.assign(n+1,0);
pre[0]=0,pre[1]=0;
for (int i = 2; i < n+1; ++i)
{
pre[i]=lca(i);
}
build(1,1,n);
while(q--){
ll type;cin>>type;
if(type==1){
ll x;cin>>x;
if(x==1)cout<<0<<endl;
else cout<<query(1,1,n,idx[x],idx[x])<<endl;
}
else{
ll x,y;cin>>x>>y;
if(x==1)continue;
upd(1,1,n,idx[x],idx[x]+sz[x]-1,y);
}
}
//}
return 0;
}