P3979 遥远的国度 题解
一棵树点有点权，支持换根、路径修改、查询子树最小值。\(n\leq 10^5\)。
这个换根其实就是，查询最小值的时候，判断一下查询点 \(x\) 相对于 \(root\) 的位置。如果 \(root\) 在 \(x\) 的子树里，就在 dfs 序里把 \(root\) 子树扣出去就行了。
我这个代码很久之前写的，找 \(x\) 的某个包含 \(root\) 的儿子好像复杂度有点问题，我感觉应该倍增，这样的话菊花是不是就死了（
点击查看代码
#include
#include
using namespace std;
typedef long long ll;
const int N=2e5+13;
const ll INF=0x3f3f3f3f3f3f3f3fll;
inline ll Min(const ll &a,const ll &b){return amaxson) maxson=siz[v],son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf,id[u]=++cnt,b[cnt]=a[u];
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
}
inline bool inr(int y,int x){return id[y]>=id[x]&&id[y]>1)
inline void refresh(int p){t[p].min=Min(t[ls].min,t[rs].min);}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){t[p].min=b[l];return;};
build(ls,l,mid),build(rs,mid+1,r);
refresh(p);
}
inline void pushup(int p,ll k){t[p].set=t[p].min=k;}
inline void pushdown(int p){
if(!t[p].set) return;
pushup(ls,t[p].set),pushup(rs,t[p].set);
t[p].set=0;
}
void update(int p,int l,int r,ll k){
if(l<=t[p].l&&t[p].r<=r) return pushup(p,k);
pushdown(p);
if(l<=mid) update(ls,l,r,k);
if(r>mid) update(rs,l,r,k);
refresh(p);
}
ll query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].min;
pushdown(p);
if(r<=mid) return query(ls,l,r);
if(l>mid) return query(rs,l,r);
return Min(query(ls,l,r),query(rs,l,r));
}
inline void t_update(int u,int v,ll w){
while(top[u]!=top[v]){
if(dep[top[u]]id[v]) Swap(u,v);
update(1,id[u],id[v],w);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i=2) res=Min(res,query(1,1,id[y]-1));
if(id[y]+siz[y]<=n) res=Min(res,query(1,id[y]+siz[y],n));
printf("%lld\n",res);
}
else printf("%lld\n",query(1,id[x],id[x]+siz[x]-1));
}
}
return 0;
}