基环树

#include<bits/stdc++.h>
#define Maxn 500000
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
ll a[Maxn+5];
int t[Maxn+5],dir[Maxn+5];
int head[Maxn+5],to[Maxn+5],nex[Maxn+5],tot;
ll mn;
int root,edge;
bool vis[Maxn+5],flag;
ll ans[Maxn+5];
void init()
{
    memset(head,-1,sizeof(head));
    tot=0;
}
void add(int x,int y)
{
    to[++tot]=y;
    nex[tot]=head[x];
    head[x]=tot;
}
void dfs2(int x,int ed)
{
    for(int i=head[x];i!=-1;i=nex[i])
    {
        if(i==ed) continue;
        ans[to[i]]=(dir[x]==dir[to[i]])?ans[x]+2*abs(a[x]-a[to[i]]):max(abs(a[x]-a[to[i]]),2*abs(a[x]-a[to[i]])-ans[x]);
        dfs2(to[i],ed);
    }
}
void dfs1(int x,int start)
{
    vis[x]=true;
    for(int i=head[x];i!=-1;i=nex[i])
    {
        if(vis[to[i]]&&to[i]!=start) continue;
        if(to[i]==start)
        {
            flag=true;
            if(dir[x]!=dir[to[i]])
            {
                if(abs(a[x]-a[to[i]])<mn)
                {
                    mn=abs(a[x]-a[to[i]]);
                    edge=i;
                    root=to[i];
                }
            }
            return ;
        }
        dfs1(to[i],start);
        if(flag)
        {
            if(dir[x]!=dir[to[i]])
            {
                if(abs(a[x]-a[to[i]])<mn)
                {
                    mn=abs(a[x]-a[to[i]]);
                    edge=i;
                    root=to[i];
                }
            }
            return ;
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        add(x,i);
        t[i]=x;
    }
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    for(int i=1;i<=n;i++) dir[i]=a[t[i]]>a[i]?1:-1;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            mn=INF;
            flag=false;
            dfs1(i,i);
            if(mn!=INF)
            {
                ans[root]=mn;
                dfs2(root,edge);
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    puts("");
    return 0;
}