### numberslayer's blog

By numberslayer, history, 7 days ago, , i was trying the question 839C - Journey in python3 and wrote a recursive program when i submitted it,it gave runtime error i tried changing recursion depth(although when i saw the test cases it passed a case with n=100000 and gave RE on n=90000) . it still didn't work then i wrote the same code in cpp and it got accepted . the same thing also happened on 580C - Kefa and Park where there was some problem with recursion not working properly .can anybody tell what is going wrong.

### python code for Journey 88623570

import math
import time
from collections import defaultdict,deque
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
from queue import PriorityQueue
import sys
sys.setrecursionlimit(10**5)
def find(curr,parent,prob,plen):
leaf=True
for i in graph[curr]:
if(i!=parent):
if(curr!=1):
find(i,curr,prob/(len(graph[curr])-1),plen+1)
else:
find(i,curr,prob/(len(graph[curr])),plen+1)
leaf=False
if(leaf):
ans+=prob*plen
graph=defaultdict(lambda:[])
for i in range(n-1):
graph[u].append(v)
graph[v].append(u)
ans=
find(1,-1,1,0)
print(ans)


### cpp code(Working) for Journey 88623478

using namespace std;
const long long A = 100000000000000LL, N = 10e5 +10;

vector<long long> a[N];
long long c[N], x, y, i, j, n, m;
double o = 0.0;

void go(int v, int pr, double prob, int len)
{
bool leaf = 1;
for (int i = 0; i < a[v].size(); i++)
if (a[v][i] != pr)
{
leaf = 0;
if (v != 0)
go(a[v][i], v, prob / double(a[v].size() &mdash; 1), len + 1);
else
go(a[v][i], v, prob / double(a[v].size()), len + 1);
}
if (leaf)
o += prob * len;
}

int main()
{
cin >> n;
for (i = 0; i < n &mdash; 1; i++)
{
scanf("%d%d", &x, &y), x--, y--, a[x].pb(y), a[y].pb(x);
}
go(0, -1, 1.0, 0);
cout << fixed << setprecision(9) << o << "\n";
}


### python code for Kefa and Park 88620540

import sys
final=
sys.setrecursionlimit(100010)
def find(curr,parent,cats):
if(cats>m):
return
ok=1
for i in graph[curr]:
if(i!=parent):
ok=0
find(i,curr,cats*a[i]+a[i])
final+=ok
graph=defaultdict(lambda:[])
for _ in range(n-1):
x-=1
y-=1
graph[x].append(y)
graph[y].append(x)
find(0,-1,a)
print(final)


### cpp code(Working) for Kefa and Park 88620695

using namespace std;
const long long A=100000000000000LL,N=228228;

vector<long long> a[N];
long long c[N],o,x,y,i,j,n,m;

void go(int v,int pr,int k){
if(k>m)return;
int ok=1;
for(int i=0;i<a[v].size();i++)if(a[v][i]!=pr)ok=0,go(a[v][i],v,k*c[a[v][i]]+c[a[v][i]]);
o+=ok;
}

int main(){
cin>>n>>m;
for(i=0;i<n;i++)scanf("%d",&c[i]);
for(i=1;i<n;i++)scanf("%d%d",&x,&y),x--,y--,a[x].pb(y),a[y].pb(x);
go(0,-1,c);
cout<<o<<"\n";
}  Comments (3)
 » Auto comment: topic has been updated by numberslayer (previous revision, new revision, compare).
 » Auto comment: topic has been updated by numberslayer (previous revision, new revision, compare).
 » yeah the same kind of problem happened with my friend, we were solving some recursive problem, then c++ worked fine, but at that time python gave him runtime error. I suggest him to use setRecursionLimit() function, but that did not work.