HDU 3078 LCA转RMQ

#include <vector> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=80010; vector<int>G[maxn]; bool vis[maxn]; int L[maxn*2],E[maxn*2],H[maxn],dis[maxn],dp[2*maxn][20],num[maxn],pre[maxn]; //H为每一个元素第1次出现的位置，E为dfs遍历的序号，L为深度，dis为每一个点到根的距离 //dp[i][j]代表的是i到j深度最小的位置 int k,n; void dfs(int t,int deep){ k++;E[k]=t;L[k]=deep;H[t]=k;//遍用时叶子在E中只会出现1次，而非叶子节点会出现屡次 for(unsigned int i=0;i<G[t].size();i++){ int tt=G[t][i]; if(!vis[tt]){//出现过就不再继续，保证dis的大小和H第1次出现的位置 pre[tt]=t; vis[tt]=1; dfs(tt,deep+1); k++;E[k]=t;L[k]=deep; } } } void RMQ_init(){//RMQ的ST算法 for(int i=1;i<=2*n⑴;i++) dp[i][0]=i; for(int i=1;(1<<i)<=2*n⑴;i++){ for(int j=1;j+(1<<i)⑴<=2*n⑴;j++){ if(L[dp[j][i⑴]]<L[dp[j+(1<<(i⑴))][i⑴]]) dp[j][i]=dp[j][i⑴]; else dp[j][i]=dp[j+(1<<(i⑴))][i⑴]; } } } int RMQ(int le,int ri){ le=H[le];ri=H[ri];//找到第1次出现的位置 if(le>ri) swap(le,ri);//le大于ri说明ri在le之前出现，交换 int kk=0; while((1<<(kk+1))<=ri-le+1) kk++; if(L[dp[le][kk]]<L[dp[ri-(1<<kk)+1][kk]]) return E[dp[le][kk]]; else return E[dp[ri-(1<<kk)+1][kk]];//返回的是dp位置的值 } int tmp[maxn]; int main(){ int q,a,b,c; while(scanf("%d%d",&n,&q)!=⑴){ for(int i=1;i<=n;i++) scanf("%d",&num[i]); for(int i=0;i<maxn;i++) G[i].clear(); memset(vis,0,sizeof(vis)); for(int i=0;i<n⑴;i++){ scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } k=0;vis[1]=1; dfs(1,1);RMQ_init(); while(q--){ scanf("%d%d%d",&a,&b,&c); if(a==0){ num[b]=c;continue; } int en=RMQ(b,c); int sum=0; while(b!=en){ tmp[sum++]=num[b]; b=pre[b]; } while(c!=en){ tmp[sum++]=num[c]; c=pre[c]; } tmp[sum++]=num[en]; if(sum<a) printf("invalid request!\n"); else{ sort(tmp,tmp+sum); printf("%d\n",tmp[sum-a]); } } } return 0; }