human
I found an interesting problem on https://codeforces.com/problemset/problem/1304/E:
Gildong was hiking a mountain, walking by millions of trees. Inspired by them, he suddenly came up with an interesting idea for trees in data structures: What if we add another edge in a tree?

Then he found that such tree-like graphs are called 1-trees. Since Gildong was bored of solving too many tree problems, he wanted to see if similar techniques in trees can be used in 1-trees as well. Instead of solving it by himself, he's going to test you by providing queries on 1-trees.

First, he'll provide you a tree (not 1-tree) with $n$ vertices, then he will ask you $q$ queries. Each query contains $5$ integers: $x$, $y$, $a$, $b$, and $k$. This means you're asked to determine if there exists a path from vertex $a$ to $b$ that contains exactly $k$ edges after adding a bidirectional edge between vertices $x$ and $y$. A path can contain the same vertices and same edges multiple times. All queries are independent of each other.
i.e. the added edge in a query is removed in the next query.

-----Input-----

The first line contains an integer $n$ ($3 \le n \le 10^5$), the number of vertices of the tree.

Next $n-1$ lines contain two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$) each, which means there is an edge between vertex $u$ and $v$. All edges are bidirectional and distinct.

Next line contains an integer $q$ ($1 \le q \le 10^5$), the number of queries Gildong wants to ask.

Next $q$ lines contain five integers $x$, $y$, $a$, $b$, and $k$ each ($1 \le x,y,a,b \le n$, $x \ne y$, $1 \le k \le 10^9$) – the integers explained in the description. It is guaranteed that the edge between $x$ and $y$ does not exist in the original tree.

-----Output-----

For each query, print "YES" if there exists a path that contains exactly $k$ edges from vertex $a$ to $b$ after adding an edge between vertices $x$ and $y$. Otherwise, print "NO".

You can print each letter in any case (upper or lower).

-----Example-----
Input
5
1 2
2 3
3 4
4 5
5
1 3 1 2 2
1 4 1 3 2
1 4 1 3 3
4 2 3 3 9
5 2 3 3...

I tried it in Python, but could not do it. Can you solve it?

 Can you provide a Python program to determine if there exists a path from vertex $a$ to $b$ that contains exactly $k$ edges after adding a bidirectional edge between vertices $x$ and $y$?
assistant
#Here is Python program to determine if there exists a path from vertex $a$ to $b$ that contains exactly $k$ edges after adding a bidirectional edge between vertices $x$ and $y$.

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

from collections import deque

class LCA():
    def __init__(self, G, root):
        self.n = len(G)
        self.dep=[0]*self.n
        self.par=[[-1]*self.n for i in range(18)]

        def bfs(root):
            que = deque()
            que.append((-1,root,0))
            while que:
                p,v,d = que.pop()
                self.dep[v]=d
                self.par[0][v]=p
                for to in G[v]:
                    if to != p:
                        que.append((v,to,d+1))

        bfs(root)

        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

    def lca(self,a,b):
        if self.dep[a]>self.dep[b]:
            a,b=b,a
        for i in range(18):
            if (self.dep[b]-self.dep[a]) & 1<<i:
                b=self.par[i][b]
        if a==b:
            return a
        for i in range(18)[::-1]:
            if self.par[i][a]!=self.par[i][b]:
                a=self.par[i][a]
                b=self.par[i][b]
        return self.par[0][a]

    def dist(self, a,b):
        lca = self.lca(a,b)
        return self.dep[a]+self.dep[b]-2*self.dep[lca]

n = int(input())
G = [[] for i in range(n)]

for i in range(n-1):
    a,b = list(map(int, input().split()))
    a,b = a-1,b-1
    G[a].append(b)
    G[b].append(a)

L = LCA(G, 0)

q = int(input())
for i in range(q):
    x,y,a,b,k = list(map(int, input().split()))
    x,y,a,b = x-1,y-1,a-1,b-1

    ab = L.dist(a,b)
    base = [ab]

    ax = L.dist(a,x)
    ay = L.dist(a,y)
    bx = L.dist(b,x)
    by = L.dist(b,y)

    base.append(ax+1+by)
    base.append(ay+1+bx)

    flag = any(ki<=k and (k-ki)%2==0 for ki in base)

    if flag:
        print("YES")
    else:
        print("NO")