p1302

Start school! I started a hard life, and I didn’t have enough vacation.

Let’s watch the problem.

Sample input Sample Input6
10
20
25
40
30
30
4 5
1 3
3 4
2 3
6 4
Sample output Sample Output90

DP on a normal tree.

Why is it a tree? The title is very clear, n nodes n-1 edges, each point has edges, not the tree can be what?

Why is DP? If I know the data of the sub-nodes, I can calculate the data of this node in a very short time, and the data of the leaf node is very good.

Why DP? This problem is a bit of aftereffect, choose or not will affect the selection of the parent node, then one more dimension, anyway, not much.

We maintain that ans1[i] represents the maximum value of I nodes, and ans0[i] represents the maximum value that is not selected. When you select, you can only add ans0 to child nodes, but you can add your own weight. Ans0 will be more relaxed. You can choose the largest nodes ans0 and ANS1.But you can’t add your own weight.

Make it an undirected edge when you read in the edge, and use a falg array when you read in the DFS to determine if you’ve experienced it, because child nodes sometimes point to the parent.

using namespace std;
int i,f,k,tx,ty;
int n;
int ans1[100010],ans0[100010],v[100010];
int tot,link[100010];
bool flag[100010];
struct node
{
    int x,y,next;
}o[200010];
void add(int x,int y)
{
    tot++;
    o[tot].x=x;
    o[tot].y=y;
    o[tot].next=link[x];
    link[x]=tot;
}
void dfs(int now)
{
    flag[now]=1;
    for(int j=link[now];j!=0;j=o[j].next)
    {
        if(flag[o[j].y])continue;
        dfs(o[j].y);
        ans1[now]+=ans0[o[j].y];
        ans0[now]+=max(ans0[o[j].y],ans1[o[j].y]);
    }
    ans1[now]+=v[now];
    return ;
}
int main()
{
ios::sync_with_stdio(false);
//freopen("123.in","r",stdin);
//freopen("123.out","w",stdout);
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    for(i=1;i<n;i++)
    {
        cin>>tx>>ty;
        add(tx,ty);
        add(ty,tx);
    }
    dfs(1);
    cout<<max(ans1[1],ans0[1]);
    return 0;
}