CodeForces 587C -> Click Here

题意

一棵树，树上节点包括一些数，可以当作一个节点的属性，问从节点 \(l\) 到节点 \(r\) 的所有数中从小到大取前 \(a\) 个 (\(a\leq10\))

思路

很好的一道练习倍增LCA题，考察了倍增思想和运用

观察到每个节点有两个属性：节点的父节点和节点包括的数组，在倍增LCA中我们把父节点的信息保存到了数组中，便于倍增查找最近公共祖先（LCA），在此题中我们还需要把节点包括的数组存到一个数组中，可以用二维 \(\tt{vector}\)????????? 存储，其他操作与查找LCA类似（就是在倍增查找LCA的基础上做亿些改动

在合并两个 \(\tt{vector}\) 时因为 \(a\leq10\) 所以只需考虑合并后的数组的前十位即可

code

#include<iostream>
#include<vector>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
int n,m,q;
vector<int> G[100005],cty[100005],num[100005][22],ans;//num存节点包括的数的信息
int dep[100005],fa[100005][22];//fa存父节点信息
vector<int> up(vector<int> &b,vector<int> &c){//合并两个vector
	int i=0,j=0;
	vector<int> a;
	a.clear();
	while(i<b.size()&&j<c.size()&&a.size()<10){//只考虑前十个数即可
		if(b[i]<c[j])a.push_back(b[i++]);
		else a.push_back(c[j++]);
	}
	while(i<b.size()&&a.size()<10){a.push_back(b[i]);i++;}
	while(j<c.size()&&a.size()<10){a.push_back(c[j]);j++;}
	return a;
}
void dfs(int x,int f,int d){
	fa[x][0]=f;fa[x][1]=fa[f][0];//get父节点信息
	num[x][0]=cty[x];num[x][1]=up(cty[x],cty[f]);//get数组信息
	dep[x]=d;
	FOR(i,0,G[x].size()){
		int u=G[x][i];
		if(u==f) continue;
		dfs(u,x,d+1);
	}
}
int main(){
	cin>>n>>m>>q;
	REP(i,1,n-1){
		int a,b;cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	REP(i,1,m){
		int a;cin>>a;
		cty[a].push_back(i);
	}
	dfs(1,0,1);
	REP(k,2,19) REP(i,1,n){
			fa[i][k]=fa[fa[i][k-1]][k-1];
			num[i][k]=up(num[i][k-1],num[fa[i][k-1]][k-1]);
		}//预处理
	REP(qq,1,q){//查询与LCA类似
		int u,v,a;
		cin>>u>>v>>a;
		ans.clear();
		if(dep[u]>dep[v]) swap(u,v);
		int step=dep[v]-dep[u];
		for(int i=19;i>=0;i--) if(step&1<<i) ans=up(ans,num[v][i]),v=fa[v][i];
		if(u==v) ans=up(ans,num[v][0]);
		else{
			for(int i=19;i>=0;i--) if(fa[u][i]!=fa[v][i]){
					ans=up(ans,num[u][i]);
					ans=up(ans,num[v][i]);
					u=fa[u][i];
					v=fa[v][i];
				}
			ans=up(ans,num[u][0]);
			if(u!=v) ans=up(ans,num[v][1]);
		}
		int len=ans.size();
		len=min(len,a);
		cout<<len<<" ";
		FOR(i,0,len) cout<<ans[i]<<" ";
		cout<<endl;
	}
	return 0;
}

C. Duff in the Army cf 587C 【倍增LCA思想应用】