[DS记录]P6779 [Ynoi2009] rla1rmdq
command_block
2021-06-28 20:04:13
**题意** ： 给定一棵 $n$ 个点的树，边有边权。
维护长为 $n$ 的序列 $A$ ，支持下列操作 ：
- 对于 $i\in[l,r]$ ，令 $A_i$ 变为 $fa(A_i)$。（特殊地，定义 $fa(rt)=rt$）
- 查询 $\min_{i\in[l,r]}dep(A_i)$
允许离线， $n,m\leq 2\times 10^5$ ，时限$\texttt{3s}$ ，空限$\texttt{64Mb}$。
------------
分块。
对于每个块记 $tag$ 为整块一起上跳的次数。
对于修改或查询中的散块，暴力计算并将 $tag$ 置为 $0$。
这需要支持快速求树上 $k$ 级祖先，可以使用重剖，额外代价为 $O(n\log n)$ ，除此之外每次询问可以看做 $O(1)$。
接下来只需考虑全局修改和询问的子问题，用于处理整块。
- 观察 ：若某个关键点 $u$ 的祖先存在其他关键点，可以忽略 $u$ 的贡献。
于是，在树上记录该点是否被经过，若某个关键点的父亲被经过，则可以将其删除。每个点只会被经过一次，这样只会移动 $O(n)$ 次。
注意，在重构块时，原先被删除的点可能再次跻身候选点之列。
对于删除的点，要打上时间戳，这样在暴力重构时就可以知道要跳多少步。
逐块处理以节省空间。时间复杂度 $O(m\sqrt{n})$ ，空间复杂度 $O(n+m)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define pb push_back
#define ll long long
#define MaxN 200500
using namespace std;
const ll INF=1ll<<60;
vector<int> g[MaxN],l[MaxN];
int siz[MaxN],dep[MaxN],fa[MaxN],tf[MaxN],mp[MaxN];
ll dis[MaxN];
void pfs1(int u)
{
siz[u]=1;
for (int i=0,v;i<g[u].size();i++)
if (!siz[v=g[u][i]]){
dep[v]=dep[fa[v]=u]+1;
dis[v]=dis[u]+l[u][i];
pfs1(v);
siz[u]+=siz[v];
if (siz[v]>siz[mp[u]])
mp[u]=v;
}
}
int dfn[MaxN],tp[MaxN],tim;
void pfs2(int u,int _tf)
{
tp[dfn[u]=++tim]=u;
tf[u]=_tf;
if (mp[u])pfs2(mp[u],_tf);
for (int i=0;i<g[u].size();i++)
if (!tf[g[u][i]])
pfs2(g[u][i],g[u][i]);
}
int rt;
int trans(int u,int k)
{
if (k>=dep[u])return rt;
k=dep[u]-k;
while(k<dep[tf[u]])u=fa[tf[u]];
return tp[dfn[u]-dep[u]+k];
}
int BS,a[MaxN],now[MaxN],tag,s[666],top;
bool vis[MaxN],flag;ll buf;
void add(int l,int r,int k)
{
int bl=k*BS,br=bl+BS;
if (r<bl||br<=l)return ;
if (l<=bl&&br-1<=r){
int tn=0;tag++;
for (int i=1;i<=top;i++){
int p=s[i];
if (a[p]==rt)flag=1;
else if (!vis[fa[a[p]]]){
vis[a[p]=fa[a[p]]]=1;
buf=min(buf,dis[a[p]]);
now[s[++tn]=p]++;
}
}top=tn;
return ;
}
for (int i=bl;i<br;i++){
a[i]=trans(a[i],tag-now[i]);
now[i]=tag;
}
l=max(l,bl);r=min(r,br-1);
int tn=0;
for (int i=1;i<=top;i++)
if (s[i]<l||r<s[i])s[++tn]=s[i];
top=tn;
for (int i=l;i<=r;i++){
a[i]=fa[a[i]];
if (a[i]==rt)flag=1;
else if (!vis[a[i]])
vis[a[s[++top]=i]]=1;
}
for (int i=bl;i<br;i++)buf=min(buf,dis[a[i]]);
}
ll qry(int l,int r,int k)
{
int bl=k*BS,br=bl+BS;
if (r<bl||br<=l)return INF;
ll ret=INF;
if (l<=bl&&br-1<=r)return buf;
for (int i=bl;i<br;i++){
a[i]=trans(a[i],tag-now[i]);
now[i]=tag;
}
l=max(l,bl);r=min(r,br-1);
for (int i=l;i<=r;i++)ret=min(ret,dis[a[i]]);
return ret;
}
struct Data{int op,l,r,p;}b[MaxN];
int n,m,q;ll ans[MaxN];
int main()
{
scanf("%d%d%d",&n,&m,&rt);
for (int i=1,u,v,w;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
g[u].pb(v);g[v].pb(u);
l[u].pb(w);l[v].pb(w);
}dep[rt]=1;fa[rt]=rt;pfs1(rt);pfs2(rt,rt);
BS=0.8*sqrt(n)+1;
for (int i=0;i<n;i++)scanf("%d",&a[i]);
for (int i=n;i<n/BS*BS+BS;i++)a[i]=1;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&b[i].op,&b[i].l,&b[i].r);
b[i].l--;b[i].r--;
if (b[i].op==2)b[i].p=++q;
}for (int i=1;i<=q;i++)ans[i]=INF;
for (int k=0;k*BS<n;k++){
memset(vis,0,sizeof(bool)*(n+5));
top=BS;tag=0;buf=INF;
int bl=k*BS,br=bl+BS;
for (int i=1;i<=BS;i++)vis[a[s[i]=bl+i-1]]=1;
for (int i=bl;i<br;i++)buf=min(buf,dis[a[i]]);
for (int i=1;i<=m;i++){
if (b[i].op==1)add(b[i].l,b[i].r,k);
else ans[b[i].p]=min(ans[b[i].p],qry(b[i].l,b[i].r,k));
}
}for (int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
```
明天也要开心哦~