2023-07-22 09:53:59 顶置3
P2633 Count on a tree
前置小知识
冷门小科技:DFS-RMQ 求LCA
最近跟着洛谷榜一的博客学了一个冷门科技：DFS序求LCA，这道题刚好要求LCA，所以就刚好适用一下。
DFS序求LCA原理：
我们令u点在dfs序中出现的位置为时间戳 \(dfn[u]\) 。
设 \(dfn[u]\) < \(dfn[v]\)。
当u不是v的祖先时，设d为\(lca(u,v)\)。
观察到\(dfn[d]\)< \(dfn[u]\) < \(dfn[v]\)，与欧拉序的祖先在u,v之间出现过不同。
但是我们找\(d\)在\(v\)方向的第一个节点\(v'\)，因为 \(dfn[u]\) < \(dfn[v]\)，所以\(dfn[v']\)属于[ \(dfn[u]\) , \(dfn[v]\)]（想一下就知道了， \(dfn[v]\)是最大的）。
那么可以得到[ \(dfn[u]\) , \(dfn[v]\)]中深度最小的节点的父亲即为d。
二：对于u是v祖先的情况，我们显然不能查 \(dfn[u]\) 了，所以我们可以查[ \(dfn[u]\) +1, \(dfn[v]\)]中深度最小的元素的最大值。
这样查对情况一,显然可以。
我们用一个倍增数组 \(fa[k][x]\) 表示从dfn为\([x,x+(1<<k)-1]\)的节点中父亲dfn最小的节点的父亲。
那对于dfn为区间\([ dfn[u] +1, dfn[v] ]\)中父亲dfn最小的节点的父亲即为 \(lca(u,v)\)。
\(Code\)
int n,m,st,fa[20][500005],dfn[500005],dn;//fa[k][x]表示dfn从[x,x+(1<<k)-1]的节点中父亲dfn最小的节点的父亲
vector<int>f[500005];// 对于u,v两个数来说，[dfn[u]+1,dfn[v]]中父亲dfn最小的即为LCA。
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
void dfs(int x,int Fa){
fa[0][dfn[x]=++dn]=Fa;
for(int y:f[x])if(y!=Fa)dfs(y,x);
}
int lca(int x,int y){
if(x==y)return x;
if((x=dfn[x])>(y=dfn[y]))x^=y^=x^=y;
int k=__lg(y-x++);
return get(fa[k][x],fa[k][y-(1<<k)+1]);
}
int main(){
n=read(),m=read(),st=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
f[u].push_back(v),f[v].push_back(u);
}
dfs(st,0);
for(int k=1;k<=__lg(n);k++)
for(int i=1;i+(1<<k)-1<=n;i++)
fa[k][i]=get(fa[k-1][i],fa[k-1][i+(1<<k-1)]);
while(m--){
printf("%d\n",lca(read(),read()));
}
}
那开始讲正题吧
因为是第k小值，我们考虑到之前做的权值可持久化线段树模板，
准备将根节点的父亲的树设置为原始树（空树），之后的树都是在原始树的基础上增加节点，实现单点修改。
然后在算排名时，我们只需要 \(x=siz[u->root]+siz[v->root]-siz[lca(u,v)->root]-siz[fa(lca(u,v))->root]\) 即可。
其他细节和模板题一样,离散，建树都一样,复杂度也一样。
P.S. 写这道题的时候真的非常的爽，没看题解，花25分钟写完微调一下就过了。应该是我写过最爽的题之一了。
（还有应该是之前写矩阵加速优化状态压缩dp）
\(Code\)
#define mid (l+r>>1)
struct tree{
int l,r,v;
}tr[5000005];
int n,m,q,a[100005],b[100005],root[100005],cnt;
int fa[23][100005],dfn[100005],dn,ans;
vector<int>f[100005];
void build(int &root,int l,int r){
root=++cnt;
if(l==r)return;
build(tr[root].l,l,mid),build(tr[root].r,mid+1,r);
}
void update(int &root,int now,int l,int r,int pos){
root=++cnt,tr[root]=tr[now],tr[root].v++;
if(l==r)return;
if(mid>=pos)update(tr[root].l,tr[now].l,l,mid,pos);
else update(tr[root].r,tr[now].r,mid+1,r,pos);
}
int query(int u,int v,int lca,int lcafa,int l,int r,int k){
if(l==r)return a[l];
int x=tr[tr[u].l].v+tr[tr[v].l].v-tr[tr[lca].l].v-tr[tr[lcafa].l].v;
if(x>=k)return query(tr[u].l,tr[v].l,tr[lca].l,tr[lcafa].l,l,mid,k);
else return query(tr[u].r,tr[v].r,tr[lca].r,tr[lcafa].r,mid+1,r,k-x);
}
void dfs(int x,int Fa){
fa[0][dfn[x]=++dn]=Fa;
int o=lower_bound(a+1,a+1+n,b[x])-a;
update(root[x],root[Fa],1,n,o);
for(int y:f[x])if(y!=Fa)dfs(y,x);
}
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
int LCA(int x,int y){
if(x==y)return x;
if((x=dfn[x])>(y=dfn[y]))x^=y^=x^=y;
int k=__lg(y-x++);//[dfn[u]+1,dfn[y]]，所以这里要加一
return get(fa[k][x],fa[k][y-(1<<k)+1]);
}
int main(){
m=read(),q=read();
for(int i=1;i<=m;i++){
a[i]=b[i]=read();
}
sort(a+1,a+1+m);
n=unique(a+1,a+1+m)-a-1;
build(root[0],1,n);
f[0].push_back(1);
for(int i=1;i<m;i++){
int u=read(),v=read();
f[u].push_back(v),f[v].push_back(u);
}
dfs(1,0);
for(int k=1;k<=__lg(m);k++)
for(int i=1;i+(1<<k)-1<=m;i++)
fa[k][i]=get(fa[k-1][i],fa[k-1][i+(1<<k-1)]);
while(q--){
int u=read()^ans,v=read(),k=read();
int lca=LCA(u,v);
ans=query(root[u],root[v],root[lca],root[fa[0][dfn[lca]]],1,n,k);
printf("%d\n",ans);
}
}