95ptsTLE#11,在线求卡常

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define push_back emplace_back
#define re register
using namespace std;

char *p1,*p2,in[100000];
#define gc() (p1 == p2 && (p2 = (p1 = in) + fread(in,1,100000,stdin),p1 == p2)?EOF:*p1++) 

inline int read()
{
	int x = 0,f = 1;
	char c = gc();
	while (c < 48 || c > 57)
	{
		if (c == '-') f = -1;
		c = gc();
	}
	while (c >= 48 && c <= 57) x = x * 10 + c - 48,c = gc();
	return x * f;
}

void write(long long x)
{
	if (x < 0) putchar('-'),x = -x; 
	if (x / 10) write(x/10);
	putchar(x%10+48); 
}

int a[200010],sz[200010],son[200010];
vector <int> g[200010],r;

void dfs1(int x)
{
    sz[x] = 1;
    for (re int i = 0;i < g[x].size();i++) 
    {
        int y = g[x][i];
        dfs1(y),sz[x] += sz[y],son[x] = sz[y] > sz[son[x]] ? y : son[x];
    }
    return;
}

void dfs2(int x,vector <int> &r)
{
    if (son[x]) dfs2(son[x],r);
    vector <int> h;
    for (re int i = 0;i < g[x].size();i++) 
        if (g[x][i] != son[x]) 
        {
            dfs2(g[x][i],h);
            for (re int i = 0;i < min(r.size(),h.size());++i) r[i] = max(r[i],h[i]);
            if (r.size() < h.size()) for (int i = r.size();i < h.size();++i) r.push_back(h[i]);
            h.clear();
        }
    r.push_back(-1);
    int cur = 0;
    while (r[cur] >= a[x]) ++cur;
    for (re int i = r.size() - 1;i > cur;i--) r[i] = r[i - 1];
    r[cur] = a[x];
    return;
}

signed main()
{
    int n = read();
    for (re int i = 1;i <= n;++i) a[i] = read();
    for (re int i = 2;i <= n;++i) g[read()].push_back(i);
    dfs1(1);
    dfs2(1,r);
    long long ans = 0;
    for (re int i = 0;i < r.size();i++) ans += r[i];
    write(ans);
    return 0;
}