mcfx's blog - LCA
/category/lca/
-
BZOJ 4539: [Hnoi2016]树
/archives/149/
2016-12-16T15:59:00+08:00
###Description
小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，其中1=k)return kth(s[a].lc,s[b].lc,l,f,k);
return kth(s[a].rc,s[b].rc,f+1,r,k-t);
}
int root[N+1];
}
int n,m,q;
namespace t1
{
int p[N+1],idm,id[N+1],idr[N+1],fa[N+1][17],dep[N+1],sz[N+1];
struct edge
{
int to,ne;
}e[N