We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
# Enter your code here. Read input from STDIN. Print output to STDOUTimportsysimportcopyn=int(raw_input())point=[int(x)forxinraw_input().split(' ')]sp=sum(point)v=set([])mi=float('inf')defdfs(p):globalmiv.add(p)r=point[p-1]forkintable[p]:ifkinv:continues=dfs(k)mi=min(mi,abs(sp-s-s))r+=sreturnrdefnr_dfs(p):globalmista=[p]whilelen(sta)>0:t=sta[-1]iflen(donetable[t])==0:r=point[t-1]forkintable[t]:#print k, tiftnotinpreork!=pre[t]:r+=valuetable[k]mi=min(mi,abs(sp-r-r))valuetable[t]=rsta.pop()forkindonetable[t]:pre[k]=tsta.append(k)donetable[k].remove(t)donetable[t]=set([])table={}foriinrange(n-1):[p,q]=[int(x)forxinraw_input().split(' ')]ifpintable:table[p].add(q)else:table[p]=set([q])ifqintable:table[q].add(p)else:table[q]=set([p])donetable=copy.deepcopy(table)valuetable={}pre={}nr_dfs(1)printmi
Cut the Tree
You are viewing a single comment's thread. Return to all comments →
thanks for advice , one time dfs