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 Link) 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)
SOLVED!!!!
Sorry for bothering anyone who was genuinely trying to help, i solved the problem by making the array static, and i was having problem to run that case on sublime as it was not responding correctly... Thank you for your patience..
BTW, if anyone know how to run your program for large testcase like in this one plz. tell me(As custom invocation only supports tc of size 256 kb) Thank you...