Network
【题目链接】Network
【题目类型】LCA dfs
&题意：
给出n个点的权值，m条边，2种操作
0 u num，将第u个点的权值改成num
k u v,询问u到v这条路上第k大的权值点
&题解：
首先可以确定的是这是一颗树,求的又是路径,所以我们可以试着用lca辅助一下(有人说为什么不用最短路,当然可以用最短路,但是时间复杂度很高,还有树上u到v点只有1条路,所以不必用最短路)
所以可以先求一下输入的u和v的lca,之后我们可以把经过的所有点找出来,之后排个序就好了,怎么找所有点呢?我们可以在dfs时用一个pre数组记录每个点的父亲是谁,这样,输入给了低下的点,又知道了lca,只要求u到lca的边,和v到lca的边就好了.
最后放到数组里一排序就ac了
求lca那块也可以用tarjan+并查集 这里用的是dfs的,其实都一样啦,因为都是只要求出u和v的lca的序号就可以了
&代码：
#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fo(i,a,b) for(int i=(a);i<=(b);i++)
#define fd(i,a,b) for(int i=(a);i>=(b);i--)
#define cle(a,v) memset(a,(v),sizeof(a))
const int maxn = 80000 + 7;
int n, q, val[maxn], He[maxn], id, fid[maxn], order[maxn * 2], depth[maxn * 2], rq[maxn * 2][20], mm[maxn * 2], pre[maxn];
struct Edge {
int to, nx;
} ed[maxn * 2];
void Ori() {
id = 0;
cle(He, -1);
}
void eAdd(int u, int v) {
ed[id].to = v, ed[id].nx = He[u];
He[u] = id++;
}
void dfs(int v, int p, int d, int& k) {
pre[v] = p;
fid[v] = k;
order[k] = v;
depth[k++] = d;
for(int j = He[v]; ~j; j = ed[j].nx) {
if(ed[j].to != p) {
dfs(ed[j].to, v, d + 1, k);
order[k] = v;
depth[k++] = d;
}
}
}
void rmqInit(int n, int b[]) {
mm[0] = -1;
for(int i = 1; i <= n; i++) {
mm[i] = (i & (i - 1)) ? mm[i - 1] : mm[i - 1] + 1;
rq[i][0] = i;
}
for(int j = 1; j <= mm[n]; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++) {
int x = rq[i][j - 1], y = rq[i + (1 << (j - 1))][j - 1];
rq[i][j] = b[x] < b[y] ? x : y;
}
}
int RMQ(int x, int y, int b[]) {
if(x > y) swap(x, y);
int k = mm[y - x + 1];
int x2 = rq[x][k], y2 = rq[y - (1 << k) + 1][k];
return b[x2] < b[y2] ? x2 : y2;
}
int LCA(int u, int v) {
return order[RMQ(fid[u], fid[v], depth)];
}
int vi[maxn], cvi;
void path(int x, int top) {
while(x != top) {
vi[cvi++] = val[x];
x = pre[x];
}
}
int main() {
freopen("E:1.in", "r", stdin);
scanf("%d%d", &n, &q);
Ori();
int u, v, op;
fo(i, 1, n) scanf("%d", &val[i]);
fo(i, 2, n) {
scanf("%d%d", &u, &v);
eAdd(u, v);
eAdd(v, u);
}
int k = 1;
dfs(1, 1, 0, k);
rmqInit(k - 1, depth);
fo(o, 1, q) {
scanf("%d%d%d", &op, &u, &v);
if(op == 0) {
val[u] = v;
}
else {
int lc = LCA(u, v);
cvi = 0;
// printf("%d
", lc);
path(u, lc);
path(v, lc);
vi[cvi++] = val[lc];
sort(vi, vi + cvi);
if(op > cvi) {
printf("invalid request!
");
}
else {
// for(int i = 0; i < cvi; i++) {
// printf("%d ", vi[i]);
// } printf("
");
printf("%d
", vi[cvi - op]);
}
}
}
return 0;
}