自动搬运

查看原文

来自洛谷，原作者为

	liuzhangfeiabc **

搬运于2025-08-24 21:57:20，当前版本为作者最后更新于2018-03-04 21:30:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

经典的带修树链第k大问题。

先说说几种道听途说的做法:

1、树剖+线段树套平衡树，查询时需要二分答案。

复杂度达到了惊人的4个log，更惊人的是据说妥妥能过。（实在懒得写写试试了qwq）

2、树剖+树状数组套主席树（或者树状数组套trie之类的），这样好处在于：主席树天生就可以直接求第k大而不用像平衡树那样二分答案。

（看似平衡树可以直接求第k大，实际上这样没法合并多棵平衡树的答案，必须得二分，而主席树不用。）

总之就是用树剖花1个log的代价把树上问题转化成序列问题，然后做法就多种多样了。

这样是3个log的，同样能过。

然后就是我写的做法：直接写树状数组套主席树。

前面几种做法都避不开树剖这一环，如果能省去这一步的话就能做到更优的复杂度。

考虑不带修的树链第k大，本质上就是查询4条链：根到u的答案+根到v的答案-根到lca的答案-根到lca父亲的答案。

所以我们可以像序列上那样建出前缀主席树，每个节点的主席树存储的是根到它路径上的所有点，然后同时查询4棵主席树就行了。

然而这样的话修改一个节点的权值会影响到它的子树内所有的节点，于是我们不得不暴力修改O（n）棵主席树。

不过既然一个点的修改只会对子树内的节点产生整体影响，我们可以考虑维护dfs序，因为一棵子树在dfs序上是一段连续的区间。

所以问题就变成了：dfs序上的区间修改，单点查询。这可以用树状数组实现。

具体操作是：把所有的主席树进行差分，差分后每棵主席树每个位置的值相当于原来它这个位置的值-原来它在dfs序上的前一棵主席树这个位置的值，这样可能会产生负数不过我们不用管。

修改时就是把区间修改转化成两个单点修改，查询时一次性查询4条链对应的前缀主席树。

于是这个题变成了两个log。

（不过据说这个题有1个log的神奇解法，不过我不会啊qwq）

上代码：

//ctsc2008 network:树上带修链上第k大
#include<bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pc putchar
#define f(i) st[0][i]
#define md int mid = l + r >> 1
#define ln t[q].ls,l,mid
#define rn t[q].rs,mid + 1,r
#define md int mid = l + r >> 1
int r(){
	int x = 0;
	char c;
	c = gc;
	while(!isdigit(c)) c = gc;
	while(isdigit(c)){
		x = (x << 1) + (x << 3) + c - '0';
		c = gc;
	}
	return x;
}
void p(int q){
	if(q >= 10) p(q / 10);
	pc(q % 10 + '0');
}
int n,m;
struct edge{
	int to,nxt;
}e[200010];
int fir[100010],cnt;
void ins(int u,int v){
	e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;
	e[++cnt].to = u;e[cnt].nxt = fir[v];fir[v] = cnt;
}
struct qry{
	int k,u,v;
}b[100010];
struct lsh{
	int a,id;
	bool bh;
}l[200010];
int ct,ct2,mx;
int dy[200010];
int fsts[100010],nxt[100010],dpt[100010],a[100010],st[20][100010];
int dfsx[100010],wz[100010],nw,sz[100010];
void dfs(int q){//打出dfs序 
	dfsx[++nw] = q;
	wz[q] = nw;
	sz[q] = 1;
	for(int i = fir[q];i;i = e[i].nxt){
		int j = e[i].to;
		if(f(q) == j) continue;
		f(j) = q;
		nxt[j] = fsts[q];
		fsts[q] = j;
		dpt[j] = dpt[q] + 1;
		dfs(j);
		sz[q] += sz[j];
	}
}
inline void buildst(){
	for(register int i = 1;i <= 17;++i){
		for(register int j = 1;j <= n;++j) st[i][j] = st[i - 1][st[i - 1][j]];
	}
} 
bool cp(lsh q,lsh w){
	return q.a < w.a;
}
int lca(int u,int v){
	if(dpt[u] < dpt[v]) swap(u,v);
	int z = dpt[u] - dpt[v],i = 0;
	while(z){
		if(z & 1) u = st[i][u];
		z >>= 1;
		++i;
	}
	if(u == v) return u;
	for(i = 17;i >= 0;--i){
		if(st[i][u] == st[i][v]) continue;
		u = st[i][u];
		v = st[i][v];
	}
	return f(u);
}
int rt[100010];
struct tree{
	int a,ls,rs;
}t[20000010];
void mdf(int &q,int l,int r,int x,int fx){//对一棵主席树进行修改 
	if(!q) q = ++ct;
	t[q].a += fx;
	if(l == r) return;
	md;
	if(x <= mid) mdf(ln,x,fx);
	else mdf(rn,x,fx);
}
void xg(int q,int x,int fx){//一个单点修改操作 
	for(int i = q;i <= n;i += (i & -i)) mdf(rt[i],1,mx,x,fx);
}
int now[100010];
int ts[100010],ft;
bool vst[100010];
int cx(int u,int v,int w,int p,int x){//查询操作，注意4条链的贡献是u + v - w - p
	int i;
	ft = 0;
	for(i = u;i;i -= (i & -i)) {
		if(vst[i]) continue;
		ts[++ft] = i;
		vst[i] = 1;
	}
	for(i = v;i;i -= (i & -i)) {
		if(vst[i]) continue;
		ts[++ft] = i;
		vst[i] = 1;
	}
	for(i = w;i;i -= (i & -i)) {
		if(vst[i]) continue;
		ts[++ft] = i;
		vst[i] = 1;
	}
	for(i = p;i;i -= (i & -i)) {
		if(vst[i]) continue;
		ts[++ft] = i;
		vst[i] = 1;
	}//提前存一下4条链会经过的树状数组节点的集合便于处理 
	for(i = 1;i <= ft;++i) now[ts[i]] = rt[ts[i]];
	int l = 1,r = mx,mid,as;
	while(l < r){
		mid = l + r >> 1;
		as = 0;
		for(i = u;i;i -= (i & -i)) as += t[t[now[i]].ls].a;
		for(i = v;i;i -= (i & -i)) as += t[t[now[i]].ls].a;
		for(i = w;i;i -= (i & -i)) as -= t[t[now[i]].ls].a;
		for(i = p;i;i -= (i & -i)) as -= t[t[now[i]].ls].a;
		if(as >= x){
			for(i = 1;i <= ft;++i) now[ts[i]] = t[now[ts[i]]].ls;
			r = mid;
		} 
		else{
			x -= as;
			for(i = 1;i <= ft;++i) now[ts[i]] = t[now[ts[i]]].rs;
			l = mid + 1;
		}
	}
	for(i = 1;i <= ft;++i) vst[ts[i]] = 0;
	return l;
}
void init(){//初始化 
	for(int i = 1;i <= n;++i){
		xg(wz[i],a[i],1);
		xg(wz[i] + sz[i],a[i],-1);
	}
}
int main(){
	int k,u,v,i,w;
	n = r();
	m = r();
	for(i = 1;i <= n;++i) {
		a[i] = r();
		l[++ct2].a = a[i];
		l[ct2].	bh = 0;
		l[ct2].id = i;
	}
	for(i = 1;i < n;++i){
		u = r();
		v = r();
		ins(u,v);
	}
	//以下是离散化部分，不过不离散化应该也行 
	for(i = 1;i <= m;++i){
		b[i].k = r();
		b[i].u = r();
		b[i].v = r();
		if(b[i].k) continue;
		l[++ct2].a = b[i].v;
		l[ct2].bh = 1;
		l[ct2].id = i;
	}
	sort(l,l + ct2 + 1,cp);
	l[0].a = -1;
	for(i = 1;i <= ct2;++i){
		if(l[i].a != l[i - 1].a) ++mx;
		if(!l[i].bh) a[l[i].id] = mx;
		else b[l[i].id].v = mx;
		dy[mx] = l[i].a;
	}
	dfs(1);
	buildst();
	init();
	for(i = 1;i <= m;++i){
		u = b[i].u,v = b[i].v,k = b[i].k;
		if(!k){
			xg(wz[u],a[u],-1);
			xg(wz[u] + sz[u],a[u],1);
			a[u] = v;
			xg(wz[u],a[u],1);
			xg(wz[u] + sz[u],a[u],-1);
		}
		else{
			w = lca(u,v);
			k = dpt[u] + dpt[v] - 2 * dpt[w] - k + 2;//这里把第k大变成了第k小 
			if(k <= 0){
				printf("invalid request!\n");
				continue;
			}	
			p(dy[cx(wz[u],wz[v],wz[w],wz[f(w)],k)]);
			putchar('\n');
		}
	}
	return 0;
}