首页 > 代码库 > LCA和RMQ题目汇总
LCA和RMQ题目汇总
1.HDU 3183
<span style="color:#000099;">A Magic LampTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1624 Accepted Submission(s): 628Problem DescriptionKiki likes traveling. One day she finds a magic lamp, unfortunately the genie in the lamp is not so kind. Kiki must answer a question, and then the genie will realize one of her dreams. The question is: give you an integer, you are allowed to delete exactly m digits. The left digits will form a new integer. You should make it minimum.You are not allowed to change the order of the digits. Now can you help Kiki to realize her dream? InputThere are several test cases.Each test case will contain an integer you are given (which may at most contains 1000 digits.) and the integer m (if the integer contains n digits, m will not bigger then n). The given integer will not contain leading zero. OutputFor each case, output the minimum result you can get in one line.If the result contains leading zero, ignore it. Sample Input178543 4 1000001 1100001 212345 254321 2 Sample Output1310123321 SourceHDU 2009-11 Programming Contest </span>
<span style="color:#000099;"></span>
<span style="color:#000099;">/*********************************
author : Grant Yuan
time : 2014/08/23 13:23:48
algorithm: RMQ
source : HDU 3183
**********************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 1005
int m,n;
char a[N];
char num[N];
int f[N][N];
int min(int i,int j)
{
return a[i]<=a[j] ? i:j;
}
void ST()
{
int i,j;
for(i=0;i<n;i++)
f[i][0]=i;
for(j=1;j<=(int)(log((double)n)/log(2.0));j++)
{
for(i=0;i+(1<<j)-1<n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
int query(int L,int R)
{
int x=(int)(log(double(R-L+1))/log(2.0));
return min(f[L][x],f[R-(1<<x)+1][x]);
}
int main()
{
int i,j,L,R;
while(~scanf("%s%d",a,&m)){
int len=strlen(a); n=len;
m=len-m;ST();
i=j=0;
while(m--){
i=query(i,len-m-1);
num[j++]=a[i++];
}
for(i=0;i<j;i++)
{
if(num[i]!='0')
break;
}
if(i==j)
{
puts("0");
continue;
}
while(i<j)
{
printf("%c",num[i]);
i++;
}
puts("");
}
return 0;
}
</span><span style="color:#000099;"></span>
<span style="color:#000099;">2.HDU 3486</span>
<span style="color:#000099;">IntervieweTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5296 Accepted Submission(s): 1240Problem DescriptionYaoYao has a company and he wants to employ m people recently. Since his company is so famous, there are n people coming for the interview. However, YaoYao is so busy that he has no time to interview them by himself. So he decides to select exact m interviewers for this task.YaoYao decides to make the interview as follows. First he queues the interviewees according to their coming order. Then he cuts the queue into m segments. The length of each segment is , which means he ignores the rest interviewees (poor guys because they comes late). Then, each segment is assigned to an interviewer and the interviewer chooses the best one from them as the employee.YaoYao’s idea seems to be wonderful, but he meets another problem. He values the ability of the ith arrived interviewee as a number from 0 to 1000. Of course, the better one is, the higher ability value one has. He wants his employees good enough, so the sum of the ability values of his employees must exceed his target k (exceed means strictly large than). On the other hand, he wants to employ as less people as possible because of the high salary nowadays. Could you help him to find the smallest m? InputThe input consists of multiple cases.In the first line of each case, there are two numbers n and k, indicating the number of the original people and the sum of the ability values of employees YaoYao wants to hire (n≤200000, k≤1000000000). In the second line, there are n numbers v1, v2, …, vn (each number is between 0 and 1000), indicating the ability value of each arrived interviewee respectively.The input ends up with two negative numbers, which should not be processed as a case. OutputFor each test case, print only one number indicating the smallest m you can find. If you can’t find any, output -1 instead. Sample Input11 3007 100 7 101 100 100 9 100 100 110 110-1 -1 Sample Output3HintWe need 3 interviewers to help YaoYao. The first one interviews people from 1 to 3, the second interviews people from 4 to 6, and the third interviews people from 7 to 9. And the people left will be ignored. And the total value you can get is 100+101+100=301>300. Source2010 ACM-ICPC Multi-University Training Contest（5）——Host by BJTU </span>
<span style="color:#000099;"> </span>
<span style="color:#000099;">/*********************************
author : Grant Yuan
time : 2014-08-24 11:54:38
algorithm: RMQ
source : HDU 3486
**********************************/
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdlib>
#include<stack>
#include<cmath>
#define INF 0x7fffffff
#define LL long long
#define mem(a) memset(a,0,sizeof(a))
#define memm(a) memset(a,1,sizeof(a))
#define rep(i,n) for(int i=0;i<n;i++)
#define repp(i,m,n) for(int i=m;i<=n;i++)
#define scd(a) scanf("%d",&a)
#define scld(a) scanf("%I64d",&a)
#define scldd(a,b) scanf("%I64d%I64d",&a,&b)
#define sclddd(a,b,c) scanf("%I64d%64d",&a,&b,&c)
#define prd(a) printf("%d\n",(int)a)
#define scf(a) scanf("%lf",&a)
#define scs(a) scanf("%s",&s)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define prdd(a,b) printf("%d %d\n",(int)a,(int)b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define prddd(a,b,c) printf("%d %d %d\n",(int)a,(int)b,(int)c)
#define scff(a,b) scanf("%lf%lf",&a,&b,&c)
#define scfff(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
#define MAX 200007
#define eps 1e-8
using namespace std;
int n,k,sum;
int a[MAX],dp[MAX][20],ans2;
bool flag;
int max(int i,int j)
{
return i>=j?i:j;
}
void build_st()
{
int i,j,temp;
temp=(int)(log(n*1.0)/log(2.0));
repp(i,1,n) dp[i][0]=a[i];
for(j=1;j<=(int)(log(n*1.0)/log(2.0));j++)
{
for(i=1;i+(1<<j)-1<=n;i++)
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
int query(int l,int r)
{
int temp=(int)(log((r-l+1)*1.0)/log(2.0));
return max(dp[l][temp],dp[r-(1<<temp)+1][temp]);
}
inline bool can(int mid)
{
int ans1=0;
int r=mid;
int i=0,j=i+r-1;
ans2=0;
while(j<n){
ans2++;
int t=query(i,j);
ans1+=a[t];
if(ans1>k) break;
i=j+1;j=i+r-1;
}
if(ans1>k) return true;
return false;
}
int main()
{
LL sum=0;
while(1){
scdd(n,k);int minr=INF;LL ans=INF;
if(n<0) break;
mem(a);mem(dp);
repp(i,1,n) {scd(a[i]);sum+=a[i];minr=min(minr,a[i]);}
if(sum<k) {printf("-1\n"); continue;}
if(k<=minr) {printf("1\n");continue;}
build_st();
int i;
int pre = -1;int len,m,aa,bb,temp;
for (i = 1; i <= n; ++i) {
len = n / i;
m = len*i;
if (len != pre) {
aa = 1;
bb = len;
ans = 0;
} else {
aa = temp + 1;
bb = temp + len;
}
while (bb <= m) {
ans += query(aa, bb);
aa += len;
bb += len;
}
if (ans > k)
break;
pre = len;
temp=m;
}
if (i > n)
printf("-1\n");
else
printf("%d\n", i);
}
return 0；}</span><span style="color:#000099;">3. POJ 3264</span>
<span style="color:#000099;"></span>
<span style="color:#000099;">Balanced LineupTime Limit: 5000MS Memory Limit: 65536K Total Submissions: 34790 Accepted: 16382 Case Time Limit: 2000MS DescriptionFor the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.InputLine 1: Two space-separated integers, N and Q. Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.OutputLines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.Sample Input6 31734251 54 62 2Sample Output630SourceUSACO 2007 January Silver </span>
<span style="color:#000099;">/*********************************
author : Grant Yuan
time : 2014-08-24 23:49:38
algorithm: RMQ
source : POJ 3264
**********************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
#define MAX 50007
using namespace std;
struct node
{
int mmin;
int mmax;
};
int a[MAX];
node dp[MAX][20];
int n,m;
void Build_St()
{
int t=(int)(log((n+1)*1.0)/log(2.0));
for(int i=1;i<=n;i++) dp[i][0].mmin=dp[i][0].mmax=a[i];
for(int j=1;j<=t;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
dp[i][j].mmin=min(dp[i][j-1].mmin,dp[i+(1<<(j-1))][j-1].mmin);
dp[i][j].mmax=max(dp[i][j-1].mmax,dp[i+(1<<(j-1))][j-1].mmax);
}
}
int Query_Min(int L,int R)
{
int t=(int)(log((R-L+1)*1.0)/log(2.0));
return min(dp[L][t].mmin,dp[R-(1<<t)+1][t].mmin);
}
int Query_Max(int L,int R)
{
int t=(int)(log((R-L+1)*1.0)/log(2.0));
return max(dp[L][t].mmax,dp[R-(1<<t)+1][t].mmax);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
//int t;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
Build_St();
int l,r;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
int ans1=Query_Max(l,r);
int ans2=Query_Min(l,r);
printf("%d\n",ans1-ans2);
}
}
return 0;
}
</span><span style="color:#000099;"></span>
<span style="color:#000099;">4.POJ 1330</span>
<span style="color:#000099;">Nearest Common AncestorsTime Limit: 1000MS Memory Limit: 10000K Total Submissions: 18569 Accepted: 9845 DescriptionA rooted tree is a well-known data structure in computer science and engineering. An example is shown below: In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is. For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y. Write a program that finds the nearest common ancestor of two distinct nodes in a tree. InputThe input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed. OutputPrint exactly one line for each test case. The line should contain the integer that is the nearest common ancestor. Sample Input2161 148 510 165 94 68 44 101 136 1510 116 710 216 38 116 1216 752 33 43 11 53 5Sample Output43SourceTaejon 2002</span><span style="color:#000099;">/*********************************
author : Grant Yuan
time : 2014-08-25 01:57:22
algorithm: LCA
source : POJ 1330
**********************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
#define MAX 10007
#define N (int)log(MAX*1.0)+1
using namespace std;
int depth[MAX],parent[30][MAX];
int root,t,n,m;
int MaxLog;
vector<int> G[MAX];
void dfs(int v,int p,int d)
{
depth[v]=d;
parent[0][v]=p;
for(int i=0;i<G[v].size();i++)
{
if(G[v][i]!=p) dfs(G[v][i],v,d+1);
}
}
void init(int V)
{
dfs(root,-1,0);
for(int k=0;k+1<MaxLog;k++)
{
for(int v=0;v<V;v++)
{
if(parent[k][v]<0) parent[k+1][v]=-1;
else parent[k+1][v]=parent[k][parent[k][v]];
}
}
}
int Lca(int u,int v)
{
while(depth[u]>depth[v]) u=parent[0][u];
while(depth[v]>depth[u]) v=parent[0][v];
while(u!=v){
u=parent[0][u];
v=parent[0][v];
}
return u;
}
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i<MAX;i++)
while(!G[i].empty()) G[i].clear();
memset(parent,-1,sizeof(parent));
memset(depth,0,sizeof(depth));
MaxLog=floor(log(n*1.0)/log(2.0));
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
parent[0][b]=a;
G[a].push_back(b);
}
for(int i=1;i<=n;i++) {if(parent[0][i]==-1) {root=i;break;}}
init(n);
int u,v;
scanf("%d%d",&u,&v);
int ans=Lca(u,v);
printf("%d\n",ans);
}
return 0;
}
</span>
<span style="color:#000099;">5.POJ 1470</span>
<span style="color:#000099;">Closest Common AncestorsTime Limit: 2000MS Memory Limit: 10000K Total Submissions: 15444 Accepted: 4942 DescriptionWrite a program that takes as input a rooted tree and a list of pairs of vertices. For each pair (u,v) the program determines the closest common ancestor of u and v in the tree. The closest common ancestor of two nodes u and v is the node w that is an ancestor of both u and v and has the greatest depth in the tree. A node can be its own ancestor (for example in Figure 1 the ancestors of node 2 are 2 and 5)InputThe data set, which is read from a the std input, starts with the tree description, in the form: nr_of_vertices vertex:(nr_of_successors) successor1 successor2 ... successorn ... where vertices are represented as integers from 1 to n ( n <= 900 ). The tree description is followed by a list of pairs of vertices, in the form: nr_of_pairs (u v) (x y) ... The input file contents several data sets (at least one). Note that white-spaces (tabs, spaces and line breaks) can be used freely in the input.OutputFor each common ancestor the program prints the ancestor and the number of pair for which it is an ancestor. The results are printed on the standard output on separate lines, in to the ascending order of the vertices, in the format: ancestor:times For example, for the following tree: Sample Input55:(3) 1 4 21:(0)4:(0)2:(1) 33:(0)6(1 5) (1 4) (4 2) (2 3)(1 3) (4 3)Sample Output2:15:5HintHuge input, scanf is recommended.SourceSoutheastern Europe 2000</span>
<span style="color:#000099;">/*********************************
author : Grant Yuan
time : 2014-08-25 16:46:12
algorithm: LCA
source : POJ 1470
**********************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#define MAX 1007
using namespace std;
int n,m,t,root;
int parent[MAX],depth[MAX],fre[MAX];
vector<int> G[MAX];
bool flag[MAX];
void dfs(int v,int p,int d)
{
parent[v]=p;
depth[v]=d;
for(int i=0;i<G[v].size();i++)
{
if(G[v][i]!=p) dfs(G[v][i],v,d+1);
}
}
void init()
{
for(int i=1;i<=n;i++) if(flag[i]==0){root=i;break;}
dfs(root,-1,0);
}
int lca(int u,int v)
{
while(depth[u]>depth[v]) u=parent[u];
while(depth[v]>depth[u]) v=parent[v];
while(u!=v){u=parent[u];v=parent[v];}
return u;
}
int main()
{
while(~scanf("%d",&n)){
memset(parent,-1,sizeof(parent));
memset(fre,0,sizeof(fre));
memset(flag,0,sizeof(flag));
memset(depth,0,sizeof(depth));
for(int i=0;i<MAX;i++) G[i].clear();
int v,m,u;
for(int k=1;k<=n;k++){
scanf("%d:(%d)",&v,&m);
for(int i=1;i<=m;i++)
{
int u;
scanf("%d",&u);
flag[u]=1;
G[v].push_back(u);
}
}
init();
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf(" (%d %d)",&v,&u);
int croot=lca(v,u);
fre[croot]++;
}
for(int i=1;i<=n;i++)
{
if(fre[i]) printf("%d:%d\n",i,fre[i]);
}
}
return 0;
}
</span><span style="color:#000099;">6.POJ 1986</span>
<span style="color:#000099;">Distance QueriesTime Limit: 2000MS Memory Limit: 30000K Total Submissions: 9411 Accepted: 3296 Case Time Limit: 1000MS DescriptionFarmer John's cows refused to run in his marathon since he chose a path much too long for their leisurely lifestyle. He therefore wants to find a path of a more reasonable length. The input to this problem consists of the same input as in "Navigation Nightmare",followed by a line containing a single integer K, followed by K "distance queries". Each distance query is a line of input containing two integers, giving the numbers of two farms between which FJ is interested in computing distance (measured in the length of the roads along the path between the two farms). Please answer FJ's distance queries as quickly as possible! Input* Lines 1..1+M: Same format as "Navigation Nightmare" * Line 2+M: A single integer, K. 1 <= K <= 10,000 * Lines 3+M..2+M+K: Each line corresponds to a distance query and contains the indices of two farms. Output* Lines 1..K: For each distance query, output on a single line an integer giving the appropriate distance. Sample Input7 61 6 13 E6 3 9 E3 5 7 S4 1 3 N2 4 20 W4 7 2 S31 61 42 6Sample Output13336HintFarms 2 and 6 are 20+3+13=36 apart. SourceUSACO 2004 February</span>
<span style="color:#000099;">/*********************************
author : Grant Yuan
time : 2014-08-26 17:50:13
algorithm: LCA
source : POJ 1986
**********************************/
#include<set>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,l,r) for(int i=l;i<=r;i++)
struct Edge{
int t,next,w;
}E[N*2];
vector< pair<int,int> > Q[N];
int s,t,w,Es,ans[N],head[N],fa[N],d[N];
bool vis[N];
int find(int i){
if(fa[i]==i) return i;
else return find(fa[i]);
}
void makelist(int s,int t,int w){
E[Es].t = t; E[Es].w = w;E[Es].next = head[s];
head[s] = Es++;
}
void LCA(int i,int w){
d[i] = w;fa[i] = i;
vis[i] = true;
for(int p=head[i];p!=-1;p=E[p].next)
if(!vis[E[p].t]){
LCA(E[p].t,w+E[p].w);
fa[E[p].t] = i;
}
int len = Q[i].size();
for(int j=0;j<len;j++){
if(vis[Q[i][j].first])
ans[Q[i][j].second] = w + d[Q[i][j].first] - 2 * d[find(Q[i][j].first)];
}
}
int n,m,qn;
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
For(i,m){
scanf("%d%d%d %*c",&s,&t,&w);
makelist(s,t,w);makelist(t,s,w);
}
scanf("%d",&qn);
For(i,qn){
scanf("%d%d",&s,&t);
Q[s].push_back(make_pair(t,i));Q[t].push_back(make_pair(s,i));
}
LCA(1,0);
For(i,qn) printf("%d\n",ans[i]);
return 0;
}
</span><span style="color:#000099;">7.HDU 2586</span>
<span style="color:#000099;">How far away ？Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5471 Accepted Submission(s): 2077Problem DescriptionThere are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people. InputFirst line is a single integer T(T<=10), indicating the number of test cases. For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n. Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j. OutputFor each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case. Sample Input23 21 2 103 1 151 22 32 21 2 1001 22 1 Sample Output1025100100 SourceECJTU 2009 Spring Contest </span><pre class="cpp" name="code"><span style="color:#000099;">/*********************************
author : Grant Yuan
time : 2014-08-25 20:54:16
algorithm: LCA
source : HDU 2586
**********************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#define MAX 100007
using namespace std;
int n,m,t,root;
int parent[MAX],depth[MAX],dis[MAX],disroot[MAX];
struct node
{
int id;
int far;
};
vector<node> G[MAX];
node s[MAX*100];
int base,top,ans;
bool flag[MAX];
void bfs(int u,int v)
{
while(top>base){
if(s[base].id==v){
ans=s[base].far;
return;
}
int m=s[base].id;int l=s[base].far;
for(int i=0;i<G[m].size();i++)
{
if(!flag[G[m][i].id]){
flag[G[m][i].id]=1;
s[top].id=G[m][i].id;
s[top++].far=l+G[m][i].far;
}
}
base++;
}
}
int main()
{
int t;
scanf("%d",&t);
int q;
while(t--){
scanf("%d%d",&n,&q);
memset(parent,-1,sizeof(parent));
memset(disroot,0,sizeof(disroot));
memset(depth,0,sizeof(depth));
memset(dis,0,sizeof(dis));
for(int i=0;i<MAX;i++) G[i].clear();
node p;
for(int i=1;i<n;i++)
{
int a,b,l;
scanf("%d%d%d",&a,&b,&l);
p.id=b;p.far=l;
G[a].push_back(p);
p.id=a;
G[b].push_back(p);
}
int u,v;
for(int i=1;i<=q;i++)
{ memset(flag,0,sizeof(flag));
scanf("%d%d",&u,&v);
top=base=0;
s[top].id=u;s[top].far=0;
top++;
bfs(u,v);
printf("%d\n",ans);
}
}
return 0;
}
</span>LCA和RMQ题目汇总
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。