洛谷题面

题目大意

给定一棵树，树上每个点有一个权值，又有 \(q\) 个询问。

对于每一个询问 u v rk，让你求出点 \(u\) 与点 \(v\) 之间的路径上的点的前 \(rk\) 小。

题目分析

考虑树上倍增，比较无脑。

我们令 \(dis[i][j][k]\) 表示从点 \(i\) 向上跳 \(2^{j}-1\) 步后第 \(k\) 小的值，再用 \(w[i][j]\) 存储城市 \(i\) 里居住的人，按编号从小到大排序。

初始化时因为从点 \(i\) 向上跳 \(0(=2^0-1)\) 步后第 \(j\) 小就是 \(w[i][j]\)，所以可以初始化出 \(dis\) 数组。

随后用类似于倍增 \(\mathbf{LCA}\) 父亲/祖先节点迭代的方法迭代即可，具体如下：

for(register int i=1;i<=n;i++)
{
	for(register int j=1;j<=10;j++)
	{
		dis[i][0][j]=w[i][j];
	}
}
	
for(register int j=1;j<=20;j++)
{
	for(register int i=1;i<=n;i++)
   	{
		for(register int k=1;k<=10;k++)
		{
			dis[i][j][k]=dis[fa[i][j-1]][j-1][k];
				
			dis[i][j][k+10]=dis[i][j-1][k];
		}
			
		sort(dis[i][j]+1,dis[i][j]+20+1);
	}
}

再来考虑怎么回答询问，不妨设当前询问为 x y rk。

令 \(lca\) 表示 \(x,y\) 的树上最近公共祖先。

将 \(res1[~],res2[~]\) 初始化为很大的数。

若 \(x=lca\)，我们倍增更新 \(y\to lca\) 的路径即可，将处理的前 \(10\) 小放在 \(res1[~]\) 中。

再将 \(w[x][i](1\le i\le 10)\) 的值放入 \(res1[~]\) 中也来更新，最后数组前 \(rk\) 个数中那些不为这个很大的数的数就是答案。

\(lca=y\) 和其他情况类似，详见代码。

注意时时排序！

代码

//2022/1/4

//2022/1/5

//2022/1/10

const int INF=0x3f3f3f3f;

const int ma=1e5+5;

struct Gragh
{
	int v;
	
	int nxt;
};

Gragh gra[ma<<1];

int head[ma],dep[ma],res1[21],res2[21];

int fa[ma][21],w[ma][21];

int dis[ma][21][21];
//dis[i][j][k]:i 向上跳 2^{j}-1 步后第 k 小的值 

int n,m,q;

int idx;

inline void add(int u,int v)
{
	gra[++idx].v=v;
	
	gra[idx].nxt=head[u];
	
	head[u]=idx;
}

inline void dfs(int now,int fath,int depth)
{
	fa[now][0]=fath;
	
	dep[now]=depth;
	
	for(register int i=1;i<=20;i++)
	{
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	
	for(register int i=head[now];i;i=gra[i].nxt)
	{
		int v=gra[i].v;
		
		if(v!=fath)
		{
			dfs(v,now,depth+1);
		}
	}
}

inline int LCA(int x,int y)
{
	if(dep[x]=0;i--)
	{
		if(dep[x]>=dep[y]+(1<=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			
			y=fa[y][i];
		}
	}
	
	return fa[x][0];
} 

inline void updata1(int x,int y)
{
	mst(res1,0x3f);
	
	for(register int i=20;i>=0;i--)
	{
		if(dep[x]>=dep[y]+(1<=0;i--)
	{
		if(dep[x]>=dep[y]+(1<