写之前觉得很恶心，写完了觉得挺好玩了，1A，棒棒哒~
题解全在代码注释中了，想清楚思路一路写下了果然没怎么卡 ^_^
/*******************************************************
Memory: 316 KB Time: 0 MS
Language: C++ (g++ 4.7.2) Result: Accepted
*******************************************************/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define PI acos(-1.0)
#define EXP exp(1.0)
#define ESP 1E-6
/**
什么恶心题！话说最后还是想不到一点无耻的看了别人的题解，竟然是暴力orz，暴力出奇迹。。果然还是太弱啊啊啊啊！
思路基本自己想的，突然觉得图论挺好玩的嘛~~
题意：n个怪物0~n-1，打死每个怪物有一个时间，怪物家族的结构是一个树形。其中n-1一定是根。如果要打死一个怪物的两个儿子，
那么就需要打死该怪物。打死怪物n-1游戏立即结束。求最长的游戏时间。
想法：这个树形结构的家族可能是一个森林。对于根不是n-1的树，全部杀死。对于n-1，杀光一颗子树，杀掉一个子儿子，
该儿子处理方式同n-1，其他儿子全部不能杀死，意味着其他儿子的儿子只能杀死一个。。。
*/
const int N = 1005;
int T[N];
vector<int> G[N];
int root[N];
int sz[N];
int one[N];
int ans[N];
int n;
// 求每个结点子树时间和（包括该点）
void dfs_sz(int v)
{
sz[v] = T[v];
for (unsigned i = 0; i < G[v].size(); ++i)
{
int u = G[v][i];
dfs_sz(u);
sz[v] += sz[u];
}
}
// 我觉得我的名字起得特别棒(不包括该节点
void dfs_one_son(int v)
{
if (one[v] != -1) return ;
int temp = 0;
int tol = 0;
for (unsigned i = 0; i < G[v].size(); ++i)
{
int u = G[v][i];
dfs_one_son(u);
tol += one[u];
}
for (unsigned i = 0; i < G[v].size(); ++i)
{
int u = G[v][i];
temp = max(temp, tol - one[u] + sz[u]);
}
one[v] = temp;
}
void dfs_solve(int v)
{
if (ans[v] != -1) return ;
int temp = 0;
int tol = 0;
if (G[v].size() == 0)
{
ans[v] = T[v];
return ;
}
if (G[v].size() == 1)
{
int u = G[v][0];
dfs_solve(u);
ans[v] = ans[u] + T[v];
return ;
}
for (unsigned i = 0; i < G[v].size(); ++i)
{
int u = G[v][i];
dfs_solve(u);
tol += one[u];
}
for (unsigned i = 0; i < G[v].size(); ++i) // 我看别人的代码就是这里。。就一眼。。没想到用两层循环。。。
{
int u = G[v][i];
for (unsigned j = 0; j < G[v].size(); ++j)
{
if (i == j) continue;
int k = G[v][j];
temp = max(temp, tol - one[u] - one[k] + sz[u] + ans[k]);
}
}
//printf("temp=%d,T[%d]=%d
", temp, v, T[v]);
ans[v] = temp + T[v];
}
int main()
{
while (~scanf("%d", &n) && n)
{
/// initialize
memset(one, -1, sizeof one);
memset(ans, -1, sizeof ans);
for (int i = 0; i <= n; ++i) G[i].clear();
/// input
for (int i = 0; i < n; ++i)
scanf("%d", &T[i]);
int a;
for (int i = 0; i < n; ++i)
{
scanf("%d", &a);
root[i] = a;
G[a].push_back(i);
}
/// solve
int res = 0;
for (int i = 0; i < n - 1; ++i)
if (root[i] == -1)
{
dfs_sz(i);
res += sz[i];
}
dfs_sz(n - 1);
dfs_one_son(n - 1);
dfs_solve(n - 1);
res += ans[n - 1];
printf("%d
", res);
// for (int i = 0; i < n; ++i)
// {
// printf("%d:%d,%d,%d
", i, sz[i], one[i], ans[i]);
// }
}
return 0;
}