fork(1) download
copy 
  1. mod=10**9+7
  2. #import resource
  3. #resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
  4. import threading
  5. threading.stack_size(2**28)
  6. import sys
  7. sys.setrecursionlimit(10**7)
  8. #fact=[1]
  9. #for i in range(1,10001):
  10. #    fact.append((fact[-1]*i)%mod)
  11. #ifact=[0]*10001
  12. #ifact[10000]=pow(fact[10000],mod-2,mod)
  13. #for i in range(10000,0,-1):
  14. #    ifact[i-1]=(i*ifact[i])%mod
  15. from sys import stdin, stdout
  16. import bisect
  17. from bisect import bisect_left as bl              #c++ lowerbound bl(array,element)
  18. from bisect import bisect_right as br             #c++ upperbound
  19. import itertools
  20. import collections
  21. import math
  22. import heapq
  23. from random import randint as rn
  24. #from Queue import Queue as Q
  25. def modinv(n,p):
  26.     return pow(n,p-2,p)
  27. def ncr(n,r,p):                        #for using this uncomment the lines calculating fact and ifact
  28.     t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
  29.     return t
  30. def ain():                           #takes array as input
  31.     return list(map(int,sin().split()))
  32. def sin():
  33.     return input().strip()
  34. def GCD(x,y):
  35.     while(y):
  36.         x, y = y, x % y
  37.     return x
  38. """*******************************************************"""
  39. def main():
  40.     def dfs(x):
  41.         p[x]=1
  42.         t=0
  43.         for i in b[x]:
  44.             if(p[i]!=1):
  45.                 r=dfs(i)
  46.                 if(r==1):
  47.                     t=1
  48.         if(t==0):
  49.             if((x==1 and len(b[x])>1) or (x!=1 and len(b[x])>2)):
  50.                 ans[0]+=1
  51.                 return 1
  52.             else:
  53.                 return -1
  54.         else:
  55.             return 1
  56.     n=int(sin())
  57.     b=[[] for i in range(n+1)]
  58.     for i in range(n-1):
  59.         x,y=ain()
  60.         b[x].append(y)
  61.         b[y].append(x)
  62.     k=0
  63.     for i in range(2,n+1):
  64.         if(len(b[i])==1):
  65.             k+=1
  66.     ans=[0]
  67.     p=[0]*(n+1)
  68.     dfs(1)
  69.     k-=ans[0]
  70.     print k
  71. ######## Python 2 and 3 footer by Pajenegod and c1729
  72. py2 = round(0.5)
  73. if py2:
  74.     from future_builtins import ascii, filter, hex, map, oct, zip
  75.     range = xrange
  76.  
  77. import os, sys
  78. from io import IOBase, BytesIO
  79.  
  80. BUFSIZE = 8192
  81. class FastIO(BytesIO):
  82.     newlines = 0
  83.     def __init__(self, file):
  84.         self._file = file
  85.         self._fd = file.fileno()
  86.         self.writable = "x" in file.mode or "w" in file.mode
  87.         self.write = super(FastIO, self).write if self.writable else None
  88.  
  89.     def _fill(self):
  90.         s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
  91.         self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
  92.         return s
  93.     def read(self):
  94.         while self._fill(): pass
  95.         return super(FastIO,self).read()
  96.  
  97.     def readline(self):
  98.         while self.newlines == 0:
  99.             s = self._fill(); self.newlines = s.count(b"\n") + (not s)
  100.         self.newlines -= 1
  101.         return super(FastIO, self).readline()
  102.  
  103.     def flush(self):
  104.         if self.writable:
  105.             os.write(self._fd, self.getvalue())
  106.             self.truncate(0), self.seek(0)
  107.  
  108. class IOWrapper(IOBase):
  109.     def __init__(self, file):
  110.         self.buffer = FastIO(file)
  111.         self.flush = self.buffer.flush
  112.         self.writable = self.buffer.writable
  113.         if py2:
  114.             self.write = self.buffer.write
  115.             self.read = self.buffer.read
  116.             self.readline = self.buffer.readline
  117.         else:
  118.             self.write = lambda s:self.buffer.write(s.encode('ascii'))
  119.             self.read = lambda:self.buffer.read().decode('ascii')
  120.             self.readline = lambda:self.buffer.readline().decode('ascii')
  121.  
  122. sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
  123. input = lambda: sys.stdin.readline().rstrip('\r\n')
  124.  
  125. #if __name__ == '__main__':
  126. #   main()
  127. threading.Thread(target=main).start()
Success #stdin #stdout #stderr 0.02s 10816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread Thread-1:
Traceback (most recent call last):
  File "/usr/lib/python2.7/threading.py", line 801, in __bootstrap_inner
    self.run()
  File "/usr/lib/python2.7/threading.py", line 754, in run
    self.__target(*self.__args, **self.__kwargs)
  File "prog.py", line 56, in main
ValueError: invalid literal for int() with base 10: ''
https://ideone.com/wQU2j6
language:
Python (cpython 2.7.16)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!