Cod sursă (job #789131)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("burlane.in");
ofstream fout("burlane.out");

const int B=317;

int n,q;

int p[100005];

vector <int> g[100005];

int block[100005];

int l[100005],r[100005];

int f[100005],d[100005];

bool viz[100005];

void dfs(int u)
{
    for(int v:g[u])
    {
        if(block[v]==block[u])
        {
            f[v]=f[u];
            d[v]=d[u]+1;
        }
        else
        {
            f[v]=u;
            d[v]=1;
        }

        dfs(v);
    }
}

int main()
{
    fin>>n>>q;
    for(int i=1; i<=n; i++)
        fin>>p[i];

    for(int i=1; i<=n; i++)
        g[p[i]].push_back(i);

    int ind=1;
    for(int i=1; i<=n; i++)
    {
        block[i]=ind;

        if(l[ind]==0)
            l[ind]=i;
        r[ind]=i;

        if(i%B==0)
            ind++;
    }

    dfs(0);

    while(q--)
    {
        int t;
        fin>>t;

        if(t==1)
        {
            int x;
            fin>>x;

            int ans=0;
            while(x>0)
            {
                ans+=d[x];
                x=f[x];
            }

            fout<<ans<<"\n";
        }
        else
        {
            int x,y;
            fin>>x>>y;

            p[x]=y;

            if(block[x]!=block[y])
            {
                f[x]=y;
                d[x]=1;
            }

            for(int i=l[block[x]]; i<=r[block[x]]; i++)
            {
                if(viz[i]==0)
                {
                    int j1=i,add=0;
                    while(block[p[j1]]==block[i] && viz[j1]==0)
                    {
                        add++;

                        j1=p[j1];
                    }

                    int j2=i;
                    while(j2!=j1 && viz[j2]==0)
                    {
                        f[j2]=f[j1];
                        d[j2]=d[j1]+add;
                        add--;

                        viz[j2]=1;

                        j2=p[j2];
                    }
                }
            }

            for(int i=l[block[x]]; i<=r[block[x]]; i++)
                viz[i]=0;
        }
    }

    return 0;
}