题解：SP2939 QTREE5 - Query on a tree V
_maojun_
·
·
题解
为什么没有树剖做法？
对于树上任意一条路径，有“路径内轻边”、“恰一端在路径上的重边”数量为 O(\log n)，这两类边直接暴力处理；“路径内重边”和“恰一端在路径上的轻边”用数据结构维护一下。
把这样的 $(x,v)$ 分成 2 类：
1. $x$ 是 $u$ 往上跳到该重链的第一个点。那么 $v$ 可以来自 $x$ 的重儿子子树，或者除了 $u$ 所在儿子外的轻儿子子树。
1. $x$ 是 $u$ 的祖先，且 $x$ 的重儿子也是 $u$ 的祖先。求 $x$ 轻儿子白点 $d(v)$ 最小值。
第 1 类点只有 $O(\log n)$ 个，查询拍到 dfs 序上是两个区间，可以简单线段树维护。
第 2 类点是 $O(\log n)$ 个区间，要实时在一个数据结构上维护着才能支持区间查询。注意到单点修改的时候子树信息有改变的轻儿子只有 $O(\log n)$ 个，直接暴力重算一下，然后拍到线段树上支持查询即可。
但这个暴力重算不能遍历所有儿子，所以搞一个支持增删查最值的数据结构即可，比如 multiset 或者两个堆。
总的复杂度就是 $O(\log^2n)$。
---
一个观察是这题求的是距离最小值，所以要是在一个更浅的 $x$（不最近的公共祖先）算了也不会影响答案，这样可以简化一点实现：第 1 类点查询的时候直接查整个子树。
加上输入输出优化可以跑到 [290ms](https://www.luogu.com.cn/record/223567591)。
```cpp
const int N=1e5+5;
int n,q;bool a[N];
const int E=N<<1;
int tot,hd[N],to[E],nxt[E];
inline void Add(int u,int v){to[++tot]=v;nxt[tot]=hd[u];hd[u]=tot;}
#define go(ck) for(int i=hd[u];i;i=nxt[i])if(int v=to[i];ck)
int M,fa[N],dep[N],sz[N],sn[N],tp[N],dfc,dfn[N];
inline void ck(int&x,int y){x>y&&(x=y);}
struct zkw{
int tr[N<<2];zkw(){memset(tr,0x3f,sizeof tr);}
void P(int p){tr[p]=min(tr[p<<1],tr[p<<1|1]);}
void U(int p,int k){tr[p=dfn[p]+M]=k;for(;p>>=1;P(p));}
int Q(int l,int r){
int x=N;for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
if(~l&1)ck(x,tr[l^1]);if(r&1)ck(x,tr[r^1]);
}return x;
}
}T1,T2;
struct Hp{
priority_queue<int,vector<int>,greater<int>>P,Q;
void ad(int x){P.emplace(x);}
void dl(int x){Q.emplace(x);}
int tp(){
while(!P.empty()&&!Q.empty()&&P.top()==Q.top()){P.pop();Q.pop();}
return P.empty()?N:P.top();
}
}H[N];int mn[N];
void dfs1(int u,int f){
fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
go(v^f){dfs1(v,u);sz[u]+=sz[v];sz[v]>sz[sn[u]]&&(sn[u]=v);}
}
void dfs2(int u,int t){
tp[u]=t;dfn[u]=++dfc;if(sn[u])dfs2(sn[u],t);
go(v^fa[u]&&v^sn[u]){dfs2(v,v);H[u].ad(mn[v]=N);}
}
inline int Q1(int u){return T1.Q(dfn[u],dfn[u]+sz[u]-1);}
inline void U2(int u){T2.U(u,a[u]?-dep[u]:H[u].tp()-2*dep[u]);}
inline void main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);Add(u,v);Add(v,u);}
dfs1(1,0);
for(M=1;M<=n;M<<=1);
for(int i=1;i<=n;i++)T1.tr[M+dfn[i]]=dep[i];
for(int i=M;i;i--)T1.P(i);
dfs2(1,1);
scanf("%d",&q);
for(int o,x;q--;){
scanf("%d%d",&o,&x);
if(!o){
T1.U(x,(a[x]^=1)?dep[x]:N);U2(x);
for(;fa[x=tp[x]];x=fa[x]){
H[fa[x]].dl(mn[x]);H[fa[x]].ad(mn[x]=Q1(x));U2(fa[x]);
}
}else{
int as=N;
for(int u=x;u;u=fa[tp[u]])
ck(as,min(Q1(u)-2*dep[u],T2.Q(dfn[tp[u]],dfn[u])));
printf("%d\n",as>n?-1:as+dep[x]);
}
}
}
```