1-Trees and Queries

题意翻译

## Description 给定一个 $n$ 个点的树,相邻点的距离为 $1$ 。 $q$ 个询问，每个询问包含五个整数： $x,y,a,b,k$。 含义是：在原树上新连上一条边 $(x,y)$ ，要求判断一下从 $a$ 点是否有距离为 $k$ 的到 $b$ 的路径。 注意： - 每个询问是独立的，即上次询问加上的边，不能为这一次的询问所用。 - 这一条路径也许会重复经过某一条边或某一点。 ## Input 第 $1$ 行： $n$ ； 第 $2 \cdots n$ 行： 每行 $2$ 个整数 $u,v$ 表示原树上有一条连接结点 $u,v$ 的边。 第 $n+1$ 行：$q$ ; 接下来 $q$ 行：每行五个整数： $x,y,a,b,k$ ，意义见上。 ## Output 共 $q$ 行。 对于每个询问，判断该路径的存在性。若存在，输出 ```YES``` ，反之输出 ```NO``` 。 ## Limits - $3\le n\le 10^5$ - $1\le q\le 10^5$ - $u,v,a,b,x,y$ 均在 $[1,n]$ 范围内。且 $u\ne v,x\ne y$。 - $k\in [1,10^9]$

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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).

输入输出样例

输入样例 #1

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 9

输出样例 #1

YES
YES
NO
YES
NO

说明

The image below describes the tree (circles and solid lines) and the added edges for each query (dotted lines). Possible paths for the queries with "YES" answers are: - $ 1 $ -st query: $ 1 $ – $ 3 $ – $ 2 $ - $ 2 $ -nd query: $ 1 $ – $ 2 $ – $ 3 $ - $ 4 $ -th query: $ 3 $ – $ 4 $ – $ 2 $ – $ 3 $ – $ 4 $ – $ 2 $ – $ 3 $ – $ 4 $ – $ 2 $ – $ 3 $

题意翻译

## Description 给定一个 $n$ 个点的树,相邻点的距离为 $1$ 。 $q$ 个询问，每个询问包含五个整数： $x,y,a,b,k$。 含义是：在原树上新连上一条边 $(x,y)$ ，要求判断一下从 $a$ 点是否有距离为 $k$ 的到 $b$ 的路径。 注意： - 每个询问是独立的，即上次询问加上的边，不能为这一次的询问所用。 - 这一条路径也许会重复经过某一条边或某一点。 ## Input 第 $1$ 行： $n$ ； 第 $2 \cdots n$ 行： 每行 $2$ 个整数 $u,v$ 表示原树上有一条连接结点 $u,v$ 的边。 第 $n+1$ 行：$q$ ; 接下来 $q$ 行：每行五个整数： $x,y,a,b,k$ ，意义见上。 ## Output 共 $q$ 行。 对于每个询问，判断该路径的存在性。若存在，输出 ```YES``` ，反之输出 ```NO``` 。 ## Limits - $3\le n\le 10^5$ - $1\le q\le 10^5$ - $u,v,a,b,x,y$ 均在 $[1,n]$ 范围内。且 $u\ne v,x\ne y$。 - $k\in [1,10^9]$