没有上司的舞会
额！！！
我在学习了半个小时的链式前向星以及树形dp（可见我有多菜啊）
学习的我一头雾水，但是终于把它做出来了！
我们先来说一下链式前向星存图，和邻接矩阵吧。
老师说，邻接矩阵是最好理解的了，（但垃圾啊）所以让我不要用，
vector也可以，但是我好像不是很理解链表这一种数据结构，所以我也不会用
邻接矩阵：
其实就像他的字面义一样，就是一个二维数组的矩阵，用来存储两个点之间的所属关系，如果这两个点之间有联系，那么便在它们的二维矩阵的交点处附上1。所以说还是比较好理解了的
但是呢，假如有五个点，那么就开一个5*5的二维矩阵，浪费的空间很多，所以我们又有了一个数据结构：链式前向星存图。
链式前向星：
若果有五个点，假设把他们想做是一个个的小房间，每个房间中藏有其他房间的钥匙，每个房间可以通往其他人的房间。现在我来讲一讲他的具体步骤吧：
有一个东西叫做st的里面存储的是第i条路的路径数。 所以呢，我们可以定一个结构体，具体代码如下：
struct Edge
{
int nxt,to,val;
}e[6001];//这一步是定义一个结构体。
void add(int a,int b,int value)
{
e[++tot].to = b;//拓展一个新的边
e[tot].val = value;//这是这条边的权值
e[tot].last = st[a];
st[a] = tot;
}
//这是每一步都要做的事哦！
顺便附上遍历的代码：
for(int st[i];i != -1;i = e[i].last)
{
}
//这样我们就可以遍历全部的点了！！！：）讲完了链式前向星存图，那么讲一下这题的思路了吧。
首先定义一个f数组，为f[i][1]和f[i][2]. f[i][1]里面存的是，假如现在的这个人不去，那么他的下属就可以去， 可以得到动态转移方程f[i][1] =sum(max(f[j][2],f[j][1]));
如果这个人要去，那么就存于f[i][2]了，可得： f[i][2] =sum(f[j][1]) + a[i];
这题就可以很轻易的得出了 最后附上代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,t,d[6001],h[6001],cnt,head[6001],f[6001][2];
struct Edge
{
int nxt,to,val;
}edge[6001];
void ins(int a,int b)
{
edge[++cnt].nxt=head[a];
edge[cnt].to=b;
head[a]=cnt;
}
void dfs(int x)
{
for(int i=head[x];i;i=edge[i].nxt)
{
int j=edge[i].to;
dfs(j);
f[x][0]+=max(f[j][1],f[j][0]);
f[x][1]+=f[j][0];
}
f[x][1]+=h[x];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>h[i];
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
d[x]++;
if(x!=0&&y!=0)
ins(y,x);
}
for(int i=1;i<=n;i++)
if (d[i]==0)
t=i;
dfs(t);
printf("%d",max(f[t][0],f[t][1]));
}