Description:

树上带修改链上第 $K$ 大。

$1\le N,Q\le 80000$

Solution:

先把树剖成链，在链上建树状数组套主席树，计算时很显然由树上查分得 $a+b-lca-fa[lca]$ ，然后就是主席树统计区间第 $K$ 大的二分方法，先把所有树的树根放到数组里然后依次处理。对于修改操作，在查询时只有他的子树会受影响，可以在 $DFS$ 序上查分，在 $L$ 处对应位置插入 $1$ ，在 $R+1$ 处对应位置插入 $-1$ ，这样前缀和即是这个点到根的路径，利用树状数组统计前缀和即可实现修改。时间复杂度 $O(Nlog^2N)$

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define INF 0x3f3f3f3f

int n,m;

#define MAXN 80010

#define HASH 3007

struct HASH_MAP

{

	int lin[HASH],nxt[MAXN << 2],dat[MAXN << 2],f[MAXN << 2],siz;

	HASH_MAP(){siz = 0;memset(lin,0,sizeof(lin));}

	int& operator [](int x)

	{

		int hsh = x % HASH;

		for(int i = lin[hsh];i != 0;i = nxt[i])

		{

			if(dat[i] == x)

			{

				return f[i];

			}

		}

		++siz;dat[siz] = x;nxt[siz] = lin[hsh];lin[hsh] = siz;

		return f[siz];

	}

}tr;

int tim[MAXN];

inline int read()

{

	int res = 0;

	char c = getchar();

	bool f;

	while((c < '0' || c > '9') && c != '-')c = getchar();

	if(c == '-'){f = true;c = getchar();}

	else{f = false;}

	while('0' <= c && c <= '9')

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return (!f ? res : -res);

}

struct edge

{

    int to,nxt;

}e[MAXN << 1];

int lin[MAXN] = {0},edgenum = 0;

inline void add(int a,int b)

{

    ++edgenum;

    e[edgenum].to = b;

    e[edgenum].nxt = lin[a];

    lin[a] = edgenum;

    return;

}

struct query

{

    int k,a,b;

}q[MAXN];

int b[MAXN << 1],to[MAXN << 1],tot = 0,cnt = 0;

inline void init()

{

	n = read();m = read();

	for(register int i = 1;i <= n;++i)

	{

		tim[i] = read();

		b[++cnt] = tim[i];

	}

	int x,y;

	for(register int i = 1;i < n;++i)

	{

		x = read();y = read();

		add(x,y);add(y,x);

	}

	for(register int i = 1;i <= m;++i)

	{

		q[i].k = read();q[i].a = read();q[i].b = read();

		if(q[i].k == 0)b[++cnt] = q[i].b;

	}

	sort(b + 1,b + 1 + cnt);

	b[0] = -INF; 

	for(register int i = 1;i <= cnt;++i)

	{

		if(b[i] != b[i - 1])

		{

			tr[b[i]] = ++tot;

			to[tot] = b[i];

		}

	}

	return;

}

int top[MAXN],siz[MAXN],fa[MAXN],dep[MAXN],son[MAXN],rank[MAXN],th[MAXN],totn = 0;

void dfs1(int k,int depth)

{

	siz[k] = 1;

	dep[k] = depth;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[son[k]] < siz[e[i].to])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	rank[k] = ++totn;th[totn] = k;

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

inline int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	if(dep[a] < dep[b])return a;

	else return b;

}

struct node

{

	int c[2],sum;

	node(){c[0] = c[1] = sum = 0;}

}t[MAXN * 400];

int ptr = 0;

inline int newnode(){return ++ptr;}

inline int lowbit(int x){return x & (-x);}

int root[MAXN];

int root_[5][MAXN];

inline void get1(int p,int *root_)

{

	root_[0] = 0;

	if(p == 0)return;

	for(register int i = p;i >= 1;i -= lowbit(i))root_[++root_[0]] = root[i];

	return;

}

inline void get2(int p,int *root_)

{

	root_[0] = 0;

	if(p == 0)return;

	for(register int i = p;i <= n;i += lowbit(i))root_[++root_[0]] = root[i];

	return;

}

void insert(int &rt,int p,int k,int l,int r)

{

	if(rt == 0)rt = newnode();

	t[rt].sum += k;

	if(l == r)return;

	int mid = ((l + r) >> 1);

	if(p <= mid)insert(t[rt].c[0],p,k,l,mid);

	else insert(t[rt].c[1],p,k,mid + 1,r);

	return;

}

inline void buildtree()

{

	for(register int i = 1;i <= n;++i)root[i] = newnode();

	for(register int i = 1;i <= n;++i)

	{

		get2(rank[i],root_[0]);

		for(register int k = 1;k <= root_[0][0];++k)insert(root_[0][k],tr[tim[i]],1,1,tot);

		get2(rank[i] + siz[i],root_[0]);

		for(register int k = 1;k <= root_[0][0];++k)insert(root_[0][k],tr[tim[i]],-1,1,tot);

	}

	return;

}

inline void work()

{

	for(register int i = 1;i <= m;++i)

	{

		if(q[i].k != 0)

		{

			int lca = LCA(q[i].a,q[i].b);

			q[i].k = dep[q[i].a] - dep[lca] + dep[q[i].b] - dep[lca] + 1 - q[i].k + 1;

			if(q[i].k <= 0)

			{

				puts("invalid request!");

				continue;

			}

			get1(rank[q[i].a],root_[1]);get1(rank[q[i].b],root_[2]);get1(rank[lca],root_[3]);get1(rank[fa[lca]],root_[4]);

			int l = 1,r = tot,res,nxt;

			while(l < r)

			{

				res = 0;

				for(register int k = 1;k <= root_[1][0];++k)if(t[root_[1][k]].c[0] != 0)res += t[t[root_[1][k]].c[0]].sum;

				for(register int k = 1;k <= root_[2][0];++k)if(t[root_[2][k]].c[0] != 0)res += t[t[root_[2][k]].c[0]].sum;

				for(register int k = 1;k <= root_[3][0];++k)if(t[root_[3][k]].c[0] != 0)res -= t[t[root_[3][k]].c[0]].sum;

				for(register int k = 1;k <= root_[4][0];++k)if(t[root_[4][k]].c[0] != 0)res -= t[t[root_[4][k]].c[0]].sum;

				if(q[i].k <= res)

				{

					nxt = 0;

					r = ((l + r) >> 1);

				}

				else

				{

					nxt = 1;

					l = ((l + r) >> 1) + 1;

					q[i].k -= res;

				}

				for(register int k = 1;k <= root_[1][0];++k)if(root_[1][k] != 0)root_[1][k] = t[root_[1][k]].c[nxt];

				for(register int k = 1;k <= root_[2][0];++k)if(root_[2][k] != 0)root_[2][k] = t[root_[2][k]].c[nxt];

				for(register int k = 1;k <= root_[3][0];++k)if(root_[3][k] != 0)root_[3][k] = t[root_[3][k]].c[nxt];

				for(register int k = 1;k <= root_[4][0];++k)if(root_[4][k] != 0)root_[4][k] = t[root_[4][k]].c[nxt];

			}

			printf("%lld\n",to[l]);

		}

		else

		{

			get2(rank[q[i].a],root_[0]);

			for(register int k = 1;k <= root_[0][0];++k)insert(root_[0][k],tr[tim[q[i].a]],-1,1,tot);

			for(register int k = 1;k <= root_[0][0];++k)insert(root_[0][k],tr[q[i].b],1,1,tot);

			get2(rank[q[i].a] + siz[q[i].a],root_[0]);

			for(register int k = 1;k <= root_[0][0];++k)insert(root_[0][k],tr[tim[q[i].a]],1,1,tot);

			for(register int k = 1;k <= root_[0][0];++k)insert(root_[0][k],tr[q[i].b],-1,1,tot);

			tim[q[i].a] = q[i].b;

		}

	}

	return;	

}

int main()

{

	init();

	dfs1(1,1);

	dfs2(1,1);

	buildtree();

	work();

	return 0;

}