脚本宝典收集整理的这篇文章主要介绍了CF587C Duff in the Army，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
洛谷题面
给定一棵树，树上每个点有一个权值，又有 (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)，我们倍增更新 (yto lca) 的路径即可，将处理的前 (10) 小放在 (res1[~]) 中。
再将 (w[x][i](1le ile 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]<dep[y])
{
swap(x,y);
}
for(register int i=20;i>=0;i--)
{
if(dep[x]>=dep[y]+(1<<i))
{
x=fa[x][i];
}
}
if(x==y)
{
return x;
}
for(register int i=20;i>=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<<i))
{
for(register int j=1;j<=10;j++)
{
res1[j+10]=dis[x][i][j];
}
sort(res1+1,res1+20+1);
x=fa[x][i];
}
}
}
inline void updata2(int x,int y)
{
mst(res2,0x3f);
for(register int i=20;i>=0;i--)
{
if(dep[x]>=dep[y]+(1<<i))
{
for(register int j=1;j<=10;j++)
{
res2[j+10]=dis[x][i][j];
}
sort(res2+1,res2+20+1);
x=fa[x][i];
}
}
}
inline void query(int x,int y,int rk)
{
int ans=0;
int lca=LCA(x,y);
if(lca==x)
{
updata1(y,x);
for(register int i=1;i<=10;i++)
{
res1[i+10]=w[x][i];
}
sort(res1+1,res1+20+1);
for(register int i=1;i<=rk;i++)
{
if(res1[i]!=INF)
{
ans++;
}
}
printf("%d ",ans);
for(register int i=1;i<=rk;i++)
{
if(res1[i]!=INF)
{
printf("%d ",res1[i]);
}
}
enter();
}
else if(lca==y)
{
swap(x,y);
updata1(y,x);
for(register int i=1;i<=10;i++)
{
res1[i+10]=w[x][i];
}
sort(res1+1,res1+20+1);
for(register int i=1;i<=rk;i++)
{
if(res1[i]!=INF)
{
ans++;
}
}
printf("%d ",ans);
for(register int i=1;i<=rk;i++)
{
if(res1[i]!=INF)
{
printf("%d ",res1[i]);
}
}
enter();
}
else
{
updata1(x,lca);
updata2(y,lca);
for(register int i=1;i<=10;i++)
{
res1[i+10]=res2[i];
}
sort(res1+1,res1+20+1);
for(register int i=1;i<=10;i++)
{
res1[i+10]=w[lca][i];
}
sort(res1+1,res1+20+1);
for(register int i=1;i<=rk;i++)
{
if(res1[i]!=INF)
{
ans++;
}
}
printf("%d ",ans);
for(register int i=1;i<=rk;i++)
{
if(res1[i]!=INF)
{
printf("%d ",res1[i]);
}
}
enter();
}
}
int main(void)
{
mst(w,0x3f);mst(dis,0x3f);
n=read(),m=read(),q=read();
for(register int i=1;i<n;i++)
{
int u=read(),v=read();
add(u,v),add(v,u);
}
for(register int i=1;i<=m;i++)
{
int x=read();
w[x][11]=i;
sort(w[x]+1,w[x]+11+1);
}
dfs(1,0,1);
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);
}
}
while(q--)
{
int u=read(),v=read(),rk=read();
query(u,v,rk);
}
return 0;
}
以上是脚本宝典为你收集整理的CF587C Duff in the Army全部内容，希望文章能够帮你解决CF587C Duff in the Army所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。