fork download
  1. from collections import deque
  2.  
  3. n = int(input())
  4.  
  5. tree = {}
  6. node = {}
  7.  
  8. for i in range(1,n+1):
  9. tree[i] = []
  10. node[i] = -1
  11.  
  12.  
  13. for i in range(n-1):
  14. u, v = [int(x) for x in input().strip().split()]
  15. tree[u].append(v)
  16. tree[v].append(u)
  17.  
  18. node[1] = 0
  19. stack = deque([1,])
  20. while len(stack)!=0:
  21. root = stack.popleft()
  22. val = node[root]
  23.  
  24.  
  25. for child in tree[root]:
  26. if node[child]==-1:
  27. node[child] = val+1
  28. stack.append(child)
  29.  
  30. # print(node)
  31. q = int(input())
  32. for _ in range(q):
  33. flag = False
  34. x, y, a, b, k = [int(x) for x in input().strip().split()]
  35. d1 = abs(node[a]-node[b])
  36. d2 = abs(node[a]-node[x])+1+abs(node[b]-node[y])
  37. d3 = abs(node[a]-node[y])+1+abs(node[b]-node[x])
  38.  
  39. if d1<=k:
  40. r = k-d1
  41. if r%2==0:
  42. flag=True
  43.  
  44. if d2<=k:
  45. r = k-d2
  46. if r%2==0:
  47. flag = True
  48.  
  49. if d3<=k:
  50. r = k-d3
  51. if r%2==0:
  52. flag = True
  53.  
  54. if flag:
  55. print("YES")
  56. else:
  57. print("NO")
Success #stdin #stdout 0.02s 9416KB
stdin
9
3 9
3 4
7 2
6 9
5 3
6 2
8 3
1 9
10
8 4 8 2 5
9 2 7 4 4
8 5 7 3 3
1 2 3 8 4
2 9 2 4 3
6 4 3 4 5
6 7 6 6 4
7 5 3 1 4
5 4 7 8 3
4 5 1 5 2
stdout
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO