First of all thanks for reading this blog..... I am trying to do dfs on a tree of size 2*(10^5) but there is some kind of error(I am sorry that i can't point out of which kind). It works for small inputs but it's not working for the above mentioned size....
DFS Code
#include<bits/stdc++.h>
#define int long long
#define double long double
#define pb emplace_back
#define pf emplace_front
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define x first
#define y second
#define endl '\n'
#define hell 998244353
#define PI 3.141592653589
#define tezz ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX 2000000000000000000
#define M 1000000007
using namespace std;
vi adj[200005];
void dfs(int v, int par){
for(int x:adj[v]){
if(x == par) continue;
dfs(x, v);
}
}
signed main()
{
tezz
int n, q;
cin>>n>>q;
for(int i=0;i<n;i++){
int x;
cin>>x;
}
for(int i=0;i<n-1;i++){
int a, b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1, 0);
}
and the test_case at which it is failing is cses tc 5. Any help will be appreciated.....
BTW the solution which i submitted for this problem is
Spoiler
#include<bits/stdc++.h>
#define int long long
#define double long double
#define pb emplace_back
#define pf emplace_front
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define x first
#define y second
#define endl '\n'
#define hell 998244353
#define PI 3.141592653589
#define tezz ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX 2000000000000000000
#define M 1000000007
using namespace std;
vi st;
vi adj[200005];
vi euler_tour;
void dfs(int v, int u){
euler_tour.pb(v);
for(int x:adj[v]){
if(x == u) continue;
dfs(x, v);
euler_tour.pb(v);
}
}
signed main()
{
tezz
int n, q;
cin>>n>>q;
mi m;
for(int i=0;i<n;i++){
int x;
cin>>x;
m[i + 1] = x;
}
for(int i=0;i<n-1;i++){
int a, b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1, 0);
mi frst, last;
vi res;
for(int i=1;i<=(int)euler_tour.size();i++){
if(!frst[euler_tour[i-1]]){
frst[euler_tour[i-1]] = (int)res.size() + 1;
last[euler_tour[i-1]] = (int)res.size() + 1;
res.pb(euler_tour[i-1]);
}
else{
last[euler_tour[i-1]] = (int)res.size();
}
}
st.assign(2*n, 0);
for(int i=0;i<n;i++) st[i+n] = m[res[i]];
for(int i=n-1;i>0;i--){
st[i] = st[i<<1] + st[i<<1|1];
}
while(q--){
int choice;
cin>>choice;
if(choice == 1){
int s, x;
cin>>s>>x;
s = frst[s] - 1;
for(st[s += n] = x; s > 1; s>>=1) st[s >> 1] = st[s] + st[s^1];
}
else{
int s;
cin>>s;
int l = frst[s] - 1;
int r = last[s];
int ans = 0;
for(l += n, r += n; l<r; l>>=1, r>>=1){
if(l & 1) ans += st[l++];
if(r & 1) ans += st[--r];
}
cout<<ans<<endl;
}
}
}
Thanks... (Sorry for my bad English)
