PROBLEM LINK:
PRACTICE
Editorialist: Tirthankar Nath
DIFFICULTY:
HARD
PREREQUISITES:
Graph BFS
PROBLEM:
Russell for his next IPL match invited his relatives. Now Russell is interested to play a game with his Nephew taking a problem of tree resembling IPL match hierarchy . So he describes the problem like,
In the tree with N leaves and Nā1 edges , where the leaves denoting match points gained previously varies from 0 to any natural number of some particular i-th team and there are N-1 pairs of leaves {ai , bi} between which there is an edge. Edge I connects leaves ai and bi . Each team in the tree has a previous point written on its leaf . Let ci be the value written on leaf i (basically team i) . Nephew will be given Q queries . The i-th query, consisting of integers qi, ei, and xi, is as follows :
- If qi=1: for each leaf v reachable from leaf aei without visiting leaf bei by traversing edges, replace cv with cv+xi.
- If qi=2: for each leaf v reachable from leaf bei without visiting leaf aei by traversing edges , replace cv with cv+xi.
After processing all queries , print total new points of each team written on each leaf ā¦
EXPLANATION:
In the given tree there are n-1 edges and each edge is connecting { , } .
In the given type of queries we can simply do BFS in each query by taking any node as root node so we choose here 1 as root node(you can take any node as root) , but if we do BFS in each query then time complexity will go beyond the time limit , so we have to think other way .
Here we will take help of the cumulative sum concept in tree and simple logic .
In the query type 1 , : said that we have to start from node and stop traversing the tree further from , so all the child nodes from w.r.t traversing from will remain unvisited , so to that nodes will not be added .
Same for query type 2 , : all child nodes under w.r.t traversing from will remain unvisited .
So from here we can say that since & are nothing but the nodes of edge so one will be just parent of another .
Taking 1 as root node if be the parent of then
For type1 query : we will traverse all nodes except node and childnodes under it , so we can undoubtedly start traversing from root 1 because starting from 1 or and follow the BFS rule and adding the value is same for both . so for our convenience will add to root value and start subtract from value of .
For type 2 query : in this case we will visit all child nodes under (w.r.t 1 as root) and no other nodes .
So we will add only to the value of since we will start traversing from root 1 so value will start adding from node .
Else if be the parent of then
For type1 query : then same will happen as per the above mentioned in type 1 query only change is will take the place of and vice-versa .
For type2 query : here also same will happen .
So at first we have to traverse through the tree taking 1 as the root node and we have to store parent of each node.
Then while performing the queries we have to follow the rule as per the above mentioned and at last we have to do BFS for time in which we will start from 1 and add those values cumulatively with each node , and to get final ans. we have to add previously given values () with the change for each node .
SOLUTION:
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define vi vector<int>
#define vvi vector<vector<int>>
#define mii map<int,int>
#define pii pair<int,int>
#define ff first
#define ss second
#define ce cout << endl ;
#define pb push_back
#define mkp make_pair
#define py cout << "YES" << endl ;
#define pn cout << "NO" << endl ;
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) ;
bool cmp(pii& a , pii& b){
int asum = a.ff + a.ss , bsum = b.ff + b.ss ;
return asum + a.ff > bsum + b.ff ;
}
const int l = 2e7 + 1 , mod = 1e9 + 7 ;
vi prime(l , 0) , phi(l + 1) , store(l , 0) ;
vvi factor(l) , adj ;
class graph{
int v ;
vector<list<int>> l ; vector<pii> mp ;
vi parent , ans , visited , a ;
public:
void create_list(int v){
this->v = v ;
l.resize(v+1) , visited.resize(v+1 , 0) ;
parent.resize(v+1) , ans.resize(v+1 , 0) ;
a.resize(v+1) ;
}
void enter_values(){
for(int i = 1 ; i <= v ; i++) cin >> a[i] ;
}
void addedge(int u , int v){
l[u].pb(v) , l[v].pb(u) ;
mp.pb(mkp(u , v)) ;
}
void print_list(){
for(int i = 1 ; i <= v ; i++){
cout << "Vertex:" << i << "->" ;
for(auto it : l[i]) cout << it << "->" ;
ce
}
}
void BFS1(){
queue<int> q ;
q.push(1) , parent[1] = 1 ;
int u ;
while(not q.empty()){
u = q.front() ;
q.pop() , visited[u] = 1 ;
for(auto it : l[u]){
if(not visited[it]){
q.push(it) ;
visited[it] = 1 , parent[it] = u ;
}
}
}
for(int i = 1 ; i <= v ; i++) visited[i] = 0 ;
}
void add(int type , int i , int val){
int u = mp[i-1].ff , v = mp[i-1].ss ;
if(type==2) swap(u , v) ;
if(parent[v]==u) ans[v] -= val , ans[1] += val ;
else ans[u] += val ;
}
void BFS2(){
queue<int> q ;
q.push(1) ;
int u ;
while(not q.empty()){
u = q.front() ;
q.pop() , visited[u] = 1 ;
for(auto it : l[u]){
if(not visited[it]){
q.push(it) ;
visited[it] = 1 , ans[it]+=ans[u] ;
}
}
}
}
void print_ans(){
for(int i = 1 ; i <= v ; i++) cout << ans[i] + a[i] << '\n' ;
}
};
void solve(){
int n ;
cin >> n ;
graph g ;
g.create_list(n) ;
g.enter_values() ;
for(int i = 0 , l , r ; i < n-1 ; i++){
cin >> l >> r ;
g.addedge(l , r) ;
}
g.BFS1() ;
int q ;
cin >> q ;
while(q--){
int type , i , val ;
cin >> type >> i >> val ;
g.add(type , i , val) ;
}
g.BFS2() ;
g.print_ans() ;
}
int32_t main() {
fio
int t = 1 ;
//cin >> t ;
while(t--) solve() ;
return 0;
}