hdu 3078
LCA，先深度深的提上来和浅的同一深度，然后继续一起提，直到相等，期间把这些路径上的点都记录下来，排序后选择即可
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ms(i, j) memset(i, j, sizeof i) using namespace std; const int MAXN = 80000 + 5, logs = 17; int n, q, val[MAXN], deep[MAXN], pre[MAXN][logs+1], tway[MAXN]; vector<int> G[MAXN]; void dfs(int x, int p) { pre[x][0] = p; for (int i=1;i<=logs;i++) pre[x][i] = pre[pre[x][i-1]][i-1]; for (int i=0;i<G[x].size();i++) { int v = G[x][i]; if (v!=p) { deep[v] = deep[x] + 1; dfs(v, x); } } } void lca(int a, int b, int k) { int lc, sum = 0; if (deep[a]>deep[b]) swap(a, b); while (deep[a]<deep[b]) { tway[++sum] = val[b]; b = pre[b][0]; } while (a!=b) { tway[++sum] = val[a]; a = pre[a][0]; tway[++sum] = val[b]; b = pre[b][0]; } tway[++sum] = val[a]; if (sum<k) {printf("invalid request!\n"); return ;} sort(tway+1, tway+1+sum); printf("%d\n", tway[sum-k+1]); } void init() { for (int i=1;i<=n;i++) { deep[i] = 0; for (int j=0;j<=logs;j++) pre[i][j] = 0; G[i].clear(); } for (int i=1;i<=n;i++) { scanf("%d", &val[i]); } for (int i=1;i<n;i++) { int x, y; scanf("%d%d", &x, &y); G[x].push_back(y), G[y].push_back(x); } } void solve() { dfs(1, 0); for (int i=1;i<=q;i++) { int x, y, k; scanf("%d%d%d", &k, &x, &y); if (k==0) val[x] = y; else lca(x,y,k); } } int main() { while (scanf("%d%d", &n ,&q)==2) { init(); solve(); } return 0; }