大意略。
思路:通过LCA/RMQ可以找到LCA(u,v),通过记录预处理前驱fa的值,可以把u->v之间的所有顶点存下来,然后排一次序找到第K大值即可,如果size < k,说明没有第K大值。
给出LCA/RMQ代码。
void DFS(int u, int dep) { vis[u] = 1; dfn[top] = dep; euler[top] = u; pos[u] = top; ++top; for(int i = 0; i < Tree[u].size(); i++) { int v = Tree[u][i]; if(vis[v]) continue; DFS(v, dep+1); dfn[top] = dep; euler[top] = u; ++top; } } void RMQ_init(int n) { for(int i = 1; i <= n; i++) d[i][0] = i; for(int j = 1; (1<<j) <= n; j++) for(int i = 1; i + (1<<j)-1 <= n; i++) { if(dfn[d[i][j-1]] < dfn[d[i + (1<<(j-1))][j-1]]) d[i][j] = d[i][j-1]; else d[i][j] = d[i + (1<<(j-1))][j-1]; } } int RMQ(int L, int R) { int k = 0; while(1<<(k+1) <= R-L+1) k++; if(dfn[d[L][k]] < dfn[d[R-(1<<k)+1][k]]) return d[L][k]; return d[R-(1<<k)+1][k]; } int LCA(int u, int v) { if(pos[u] > pos[v]) swap(u, v); return euler[RMQ(pos[u], pos[v])]; }