P6779 题解

· · 题解

考虑分块。

注意到空间可能比较大，可以选择按块处理。

那么对于一个块，从前往后枚举询问：

遇到一个区间无交的询问，忽略

遇到一个散块询问，暴力重构这个块

遇到一个整块询问，考虑维护一个链表，因为如果它的父亲被占用了，那么它就没用了，因为都是整块跳。那么每次扫一遍链表，可以证明它的复杂度均摊是对的。

复杂度 O(m(S+\dfrac{n}{S}))

有一些细节要注意，这里放一个不卡常的代码

#include<bits/stdc++.h>
using namespace std;
int tot=0,bg[200005],gb[200005],fa[200005],ffa[200005],sz[200005],dep[200005];
int a[200005],bl[200005],bs[1005],es[1005];
int n,m,rt,cs[1005],l1[200005],l2[200005],jt[200005],vist[200005];
int OP[200005],L[200005],R[200005],vvv[200005];
vector<pair<int,int> >g[200005];
long long dist[200005],ans[200005],ZXZ;
void dfs(int x,int la)
{
    sz[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        int cu=g[x][i].first,c2=g[x][i].second;
        if(cu==la)continue;
        dist[cu]=dist[x]+c2,dep[cu]=dep[x]+1;
        dfs(cu,x);
        sz[x]+=sz[cu],fa[cu]=x;
    }
}
void dfs2(int x,int la)
{
    bg[x]=++tot,gb[bg[x]]=x;
    if(sz[x]==1)return;
    int ans=0,w;
    for(int i=0;i<g[x].size();i++)
    {
        int cu=g[x][i].first,c2=g[x][i].second;
        if(cu==la)continue;
        if(ans<sz[cu])ans=sz[cu],w=cu;
    }
    ffa[w]=ffa[x],dfs2(w,x);
    for(int i=0;i<g[x].size();i++)
    {
        int cu=g[x][i].first,c2=g[x][i].second;
        if(cu==la||cu==w)continue;
        ffa[cu]=cu,dfs2(cu,x);
    }
}
void jum(int x,int le)
{
    if(!le)return;
    int y=a[x];
    while(ffa[y]!=rt&&le>dep[y]-dep[ffa[y]])
    {
        le-=dep[y]-dep[ffa[y]]+1;
        y=fa[ffa[y]];
    }
    if(dep[y]<le)y=rt;
    else y=gb[bg[y]-le];
    a[x]=y;
}
void chonggou(int x,int l,int r)
{
    ZXZ=LLONG_MAX;
    for(int i=bs[x];i<=es[x];i++)
    {
        int dd=cs[x]-vvv[i];
        if(l<=i&&i<=r)jum(i,dd+1);
        else jum(i,dd);
        ZXZ=min(ZXZ,dist[a[i]]);
    }
    cs[x]=0;
    for(int i=bs[x];i<=es[x];i++)l1[i]=i-1,l2[i]=i+1,vvv[i]=0;
    l1[bs[x]]=l2[es[x]]=0;
    l1[bs[x]]=n+1,l2[n+1]=bs[x];
}
int main()
{
    cin>>n>>m>>rt;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u].push_back(make_pair(v,w));
        g[v].push_back(make_pair(u,w));
    }
    fa[rt]=rt,dfs(rt,0);
    ffa[rt]=rt,dfs2(rt,0);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int S=sqrt(n+0.5),SS=(n-1)/S+1;
    for(int i=1;i<SS;i++)
    {
        bs[i]=(i-1)*S+1,es[i]=i*S;
        for(int j=bs[i];j<=es[i];j++)bl[j]=i;
    }
    bs[SS]=(SS-1)*S+1,es[SS]=n;
    for(int j=bs[SS];j<=es[SS];j++)bl[j]=SS;
    int gs=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&OP[i],&L[i],&R[i]);
        if(OP[i]==2)gs++;
    }
    memset(ans,63,sizeof(ans));
    for(int i=1;i<=SS;i++)
    {
        ZXZ=LLONG_MAX;
        for(int j=bs[i];j<=es[i];j++)
            l1[j]=j-1,l2[j]=j+1,vvv[j]=0,ZXZ=min(ZXZ,dist[a[j]]);
        l1[bs[i]]=l2[es[i]]=0;
        l1[bs[i]]=n+1,l2[n+1]=bs[i];
        for(int j=1;j<=m;j++)
        {
            int op=OP[j],l=L[j],r=R[j];
            if(es[i]<l||bs[i]>r)continue;
            if(l<=bs[i]&&es[i]<=r)
            {
                if(op==2)
                {
                    ans[j]=min(ans[j],ZXZ);
                    continue;
                }
                cs[i]++;
                for(int k=l2[n+1];k;k=l2[k])
                {
                    if(vist[fa[a[k]]]==i)
                    {
                        int pr=l1[k],nx=l2[k];
                        l2[pr]=nx,l1[nx]=pr;
                    }else
                    {
                        a[k]=fa[a[k]];
                        vvv[k]++;
                        vist[a[k]]=i;
                        ZXZ=min(ZXZ,dist[a[k]]);
                    }
                }
            }else
            {
                int ll=max(l,bs[i]),rr=min(r,es[i]);
                if(op==1)chonggou(i,ll,rr);
                else
                {
                    chonggou(i,-1,-1);
                    long long aa=LLONG_MAX;
                    for(int k=ll;k<=rr;k++)aa=min(aa,dist[a[k]]);
                    ans[j]=min(ans[j],aa);
                }
            }
        }
    }
    for(int i=1;i<=m;i++)if(OP[i]==2)printf("%lld\n",ans[i]);
    return 0;
}