hdu3078(lca / RMQ在线)
生活随笔
收集整理的這篇文章主要介紹了
hdu3078(lca / RMQ在线)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目鏈接: http://acm.hdu.edu.cn/showproblem.php?pid=3078
題意: 給出一棵 n 個點的帶點權值的樹, 接下來有 q 組形如 k, x, y 的輸入, 若 k == 0 則將 x 點的權值替換成 y, 否則輸出 x 到 y 之間頂點地 k 大的權值.
思路: 用一個數組 val 記錄一下每個頂點的權值, 對于k == 0, 直接令 val[x] = y 即可 .
對于詢問, 可以先求出 lca, 再記錄一下路徑上的頂點的權值, sort 一下, 輸出第 k 大的即可.
代碼:
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std; const int MAXN = 8e4 + ;
vector<int> vt[MAXN];
int dp[MAXN << ][];
int first[MAXN], ver[MAXN << ], deep[MAXN << ];
int pre[MAXN], val[MAXN], yy[MAXN], ip = , indx = ; bool cmp(int x, int y){
return x > y;
} void dfs(int u, int h, int fa){
pre[u] = fa;
ver[++indx] = u;
deep[indx] = h;
first[u] = indx;
for(int i = ; i < vt[u].size(); i++){
int v = vt[u][i];
if(v != fa){
dfs(v, h + , u);
ver[++indx] = u;
deep[indx] = h;
}
}
} void ST(int n){
for(int i = ; i <= n; i++){
dp[i][] = i;
}
for(int j = ; ( << j) <= n; j++){
for(int i = ; i + ( << j) - <= n; i++){
int x = dp[i][j - ], y = dp[i + ( << (j - ))][j -];
dp[i][j] = deep[x] < deep[y] ? x : y;
}
}
} int RMQ(int l, int r){
int len = log2(r - l + );
int x = dp[l][len], y = dp[r - ( << len) + ][len];
return deep[x] < deep[y] ? x : y;
} int LCA(int x, int y){
int l = first[x];
int r = first[y];
if(l > r) swap(l, r);
int pos = RMQ(l, r);
return ver[pos];
} void path(int x, int root, int &pos){
while(x != root && x != -){
yy[pos++] = val[x];
x = pre[x];
}
} void solve(int x, int y, int k){
int pos = , lca = LCA(x, y);
path(x, lca, pos);
path(y, lca, pos);
yy[pos++] = val[lca];
if(pos < k) puts("invalid request!");
else{
sort(yy, yy + pos, cmp);//注意是從大到小的第 k 大!!!!!!!!!
printf("%d\n", yy[k - ]);
}
} int main(void){
int n, q, x, y, op;
scanf("%d%d", &n, &q);
for(int i = ; i <= n; i++){
scanf("%d", &val[i]);
}
for(int i = ; i < n; i++){
scanf("%d%d", &x, &y);
vt[x].push_back(y);
vt[y].push_back(x);
}
dfs(, , -);
ST(indx);
while(q--){
scanf("%d%d%d", &op, &x, &y);
if(!op) val[x] = y;
else solve(x, y, op);
}
return ;
}
總結
以上是生活随笔為你收集整理的hdu3078(lca / RMQ在线)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 不论在哪种政治体制下，执政党都很注重稳定
- 下一篇： 上24小时，休息24小时，没有节假日，合