UPC 1017 Easy Tree Query （二叉搜索树）

题目描述

You are given a binary search tree with depth k, whose nodes are valued from 1 to (2k − 1) and then Q queries.For each query, you are given p nodes. Find the root of a smallest subtree which contains all p nodes and print its value.

输入

The first line of input contains an integer T (T ≤ 100), the number of test cases. The first line of each test case contains two integers k (1 ≤ k ≤ 60) and Q (1 ≤ Q ≤ 10 4 ). In next Q lines, each line contains an integer p and then p integers — the values of nodes in this query. It is guaranteed that the total number of nodes given in each test case will not exceed 105.

输出

For each query, print a line contains the answer of that query.

样例输入

14 13 10 15 13

样例输出

12

题意

在深度为 ​​k​​​ 的二叉搜索树中，给出 ​​q​​ 次查询，输出每次查询节点的最近共同祖先。

思路

二叉搜索树有这样一个性质，即把树上所有节点从左到右依次输出其值刚好是排序的。

我们可以先对所要查询的点排序，设定 ​​root​​ 为当前判断的根节点。

若​​a[0]<=root&&a[n-1]>=root​​​ ，说明这些点遍布在​​root​​​ 的两棵子树中，此时最近公共祖先便是​​root​​ 咯！若​​a[0]>root​​​ ，说明所有节点都在​​root​​​ 的右子树中，更新​​root​​ 为其右孩子节点，返回第一步。若​​a[n-1]

AC 代码

#include #include #include #include #include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f#define MAXN 1000005#define Mod 1000000007using namespace std;typedef unsigned long long LL;LL a[MAXN];int main(){ int T; scanf("%d",&T); while(T--) { int k,q; scanf("%d%d",&k,&q); while(q--) { int n; scanf("%d",&n); for(int i=0; i=root) { printf("%llu\n",root); break; } if(a[n-1]root) { t--; root+=(LL)1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。