Split The Tree

#include<bits/stdc++.h>
#define N 100050
using namespace std;

vector<int>edge[N];
int w[N];
int children[N]={0},number[N]={0},dfsorder[N],len=0;

int dfs(int x)
{
    dfsorder[++len]=x;
    number[x]=len;
    children[x]=1;

    int Size=edge[x].size();
    for(int i=0;i<Size;i++)
    if(number[edge[x][i]]==0)
    {
        children[x]+=dfs(edge[x][i]);
    }
    return children[x];
}

struct ss
{
    int l,r,index,ans;

    bool operator < (const ss& s) const
    {
        return r<s.r;
    }
};
vector<ss>interval;

int c[2*N+5]={0};
void updata(int x,int v)
{
    for(int i=x;i<2*N;i+=i&(-i))c[i]+=v;
}

int Sum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=x&(-x);
    }
    return ans;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int p;
        scanf("%d",&p);
        edge[i].push_back(p);
        edge[p].push_back(i);
    }

    for(int i=1;i<=n;i++)scanf("%d",&w[i]);

    dfs(1);

    for(int i=1;i<=n;i++)
    {
       interval.push_back((ss){number[i],number[i]+children[i]-1,i,0});
       interval.push_back((ss){number[i]+children[i],n+number[i]-1,i,0});
    }
    for(int i=1;i<=n;i++)
    {
        dfsorder[i]=w[dfsorder[i]];
        dfsorder[n+i]=dfsorder[i];
    }
    sort(interval.begin(),interval.end());

    int last[N]={0};
    int c1=1;

    for(int i=0;i<2*n;i++)
    {
        if(interval[i].l>interval[i].r)continue;

        for(int j=c1;j<=interval[i].r;j++)
        {
            if(last[dfsorder[j]]==0)
            {
                updata(j,1);
                last[dfsorder[j]]=j;
            }
            else
            {
                updata(last[dfsorder[j]],-1);
                updata(j,1);
                last[dfsorder[j]]=j;
            }
        }
        interval[i].ans=Sum(interval[i].r)-Sum(interval[i].l-1);
        c1=interval[i].r+1;
    }

    int sum[N]={0},ans=0;

    for(int i=0;i<2*n;i++)
    {
        sum[interval[i].index]+=interval[i].ans;
        ans=max(ans,sum[interval[i].index]);
    }

    printf("%d\n",ans);
    return 0;
}