【洛谷P6071】[MdOI2020]Treequery
可持久化线段树，倍增，ST 表。
题目大意：
给定一棵树，边带权。每次询问给出 $p,l,r$，问 $p$ 到编号 $[l,r]$ 中所有点的简单路径的交的长度。
强制在线。
题解：
简单数据结构题。
我们保留编号在 $[l,r]$ 之间的点以及它们中间的点和边，若 $p$ 在这其中，则简单路径无交。若 $p$ 在这之外，则简单路径有交。
考虑求出那个开始相交的点。
我们先钦定一个点作为树根，然后，令包含 $[l,r]$ 所有结点的最小连通块中，深度最小的结点为 $d$。这个 $d$ 是 $[l,r]$ 所有结点的最近公共祖先。
考虑如何求 $d$。由于 $\mathrm{LCA}(x,y)$ 满足结合律（$\mathrm{LCA}(\mathrm{LCA}(x,y),z)=\mathrm{LCA}(x,\mathrm{LCA}(y,z))$）和幂等律（$\mathrm{LCA}(x,x)=x$），所以是可以用 ST 表来维护的。预处理时间复杂度 $O(n\log^2 n)$ 或 $O(n\log n)$ 或 $O(n)$，查询时间复杂度 $O(\log n)$ 或 $O(1)$。
$p$ 和 $d$ 的位置关系有两种：
$p$ 在 $d$ 的子树外（$\mathrm{LCA}(p,d)\neq d$）。此时 $d$ 到 $p$ 的简单路径就是 $p$ 到 $[l,r]$ 的路径的相交部分。直接计算距离即可。
$p$ 在 $d$ 的子树内（$\mathrm{LCA(p,d)=d}$）。
若 $p$ 的子树中存在 $[l,r]$ 内的点，则说明 $p$ 在连通块内部，此时无交的部分。
若 $p$ 的子树中不存在 $[l,r]$ 内的点，则说明 $p$ 在连通块内部。我们要找到距离 $p$ 最近的在连通块内的结点 $d’$。这个 $d’$ 一定是 $p$ 的祖先。
我们可以通过倍增的方法找到 $d’$。
至于如何判断子树内有没有 $[l,r]$ 内的点，我们可以建可持久化线段树，每棵线段树维护 $[1,i]$ 结点的出现情况（线段树里存 dfs 序），然后只要判断这棵子树的 dfs 序区间里是否存在点即可。预处理 $O(n\log n)$，单次查询 $O(\log n)$。
外层还要套一个倍增，因此查询的总时间复杂度 $O(q\log^2 n)$。
Code：
#include<iostream>
using namespace std;
const int N=2e5+5;
#define lg2(x)(31^__builtin_clz(x))
int n,m,head[N],cnt,dfn[N],idx,top[N],fa[N],F[19][N],sz[N],son[N],dep[N],ans,dis[N];
struct edge{
int to,nxt,w;
}e[N<<1];
int ls[N*33],rs[N*33],siz[N*33],nod,st[19][N],rt[N];
void insert(int&o,int pre,int l,int r,const int&pos){
o=++nod;
siz[o]=siz[pre]+1;
if(l<r){
const int mid=l+r>>1;
if(pos<=mid)insert(ls[o],ls[pre],l,mid,pos),rs[o]=rs[pre];
else insert(rs[o],rs[pre],mid+1,r,pos),ls[o]=ls[pre];
}
}
int query(int ld,int rd,int l,int r,const int&L,const int&R){
if(!ld&&!rd)return 0;
if(L<=l&&r<=R)return siz[rd]-siz[ld];
const int mid=l+r>>1;
int ret=0;
if(L<=mid)ret=query(ls[ld],ls[rd],l,mid,L,R);
if(mid<R)ret+=query(rs[ld],rs[rd],mid+1,r,L,R);
return ret;
}
void dfs(int now){
for(int i=1;i<19;++i)F[i][now]=F[i-1][F[i-1][now]];
sz[now]=1,son[now]=0;
for(int i=head[now];i;i=e[i].nxt)
if(!dep[e[i].to]){
dis[e[i].to]=dis[now]+e[i].w;
dep[e[i].to]=dep[now]+1;
F[0][e[i].to]=fa[e[i].to]=now;
dfs(e[i].to);
sz[now]+=sz[e[i].to];
if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
}
}
void dfs2(int now){
dfn[now]=++idx;
if(son[now])top[son[now]]=top[now],dfs2(son[now]);
for(int i=head[now];i;i=e[i].nxt)
if(e[i].to!=son[now]&&dep[e[i].to]>dep[now])
dfs2(top[e[i].to]=e[i].to);
}
inline int LCA(int x,int y){
if(!x||!y)return 0;
while(top[x]!=top[y])
if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
return dep[x]<dep[y]?x:y;
}
inline int ask(int l,int r){
const int g=lg2(r-l+1);
return LCA(st[g][l],st[g][r-(1<<g)+1]);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<n;++i){
int u,v,w;
cin>>u>>v>>w;
e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
}
dfs(dep[1]=1),dfs2(top[1]=1);
for(int i=1;i<=n;++i)st[0][i]=i,insert(rt[i],rt[i-1],1,n,dfn[i]);
for(int i=1;i<19;++i)
for(int j=1;j<=n;++j)
st[i][j]=LCA(st[i-1][j],st[i-1][j+(1<<(i-1))]);
while(m--){
int x,l,r;
cin>>x>>l>>r;
x^=ans,l^=ans,r^=ans;
int lt=ask(l,r),ls=LCA(lt,x);
if(ls!=lt)ans=dis[lt]-dis[ls]+dis[x]-dis[ls];else
if(query(rt[l-1],rt[r],1,n,dfn[x],dfn[x]+sz[x]-1))ans=0;else{
int y=x;
for(int i=18;~i;--i)
if(F[i][y]&&!query(rt[l-1],rt[r],1,n,dfn[F[i][y]],dfn[F[i][y]]+sz[F[i][y]]-1))y=F[i][y];
ans=dis[x]-dis[fa[y]];
}
cout<<ans<<'\n';
}
return 0;
}