Blue Bridge Cup 2015 preliminaries tree of life DFS diagram

Everyone thinks that writing is OK. You can praise, collect and pay attention to it!
You can also come to mine Personal blog Visit, it is estimated that it will be updated in recent years! Make friends with me! https://motongxue.cn

Blue Bridge Cup 2015 preliminaries tree of life 😁

Title Description

In the X forest, God created the tree of life.
He marked an integer on each node (leaf is also called a node) of each tree to represent the harmony value of this point.
God wants to select a non empty node set s in this tree, so that there is a point column {a, v1, v2,..., vk, b} for any two points a and B in S
So that each point in this point column is an element in S, and there is an edge between two adjacent points in the sequence.
On this premise, God wants to make the sum of integers corresponding to points in S as large as possible.
The biggest sum is God's score for the tree of life.
Through the efforts of atm, he has known the integer on each node of each tree given by God.
But because atm is not good at computing, he doesn't know how to score effectively.
He needs you to write a program for him to calculate the score of a tree.

input

An integer n in the first line indicates that the tree has n nodes. (0<n<=10^5)
The second line contains n integers, which represent the score of each node in turn. (the score of each node shall not exceed 10 ^ 6)
Next, n-1 lines, with 2 integers u and V in each line, indicate that there is an edge from u to v.
Since this is a tree, there is no ring.

output

Output a number on each line, indicating the score God gave the tree.

sample input

5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

sample output

8

analysis

From the drawing of the title:

analysis

  1. Because there are n nodes and n-1 edges, this graph can finally form a tree
  2. We can pick up a node in the graph and take it as the root of the tree formed by the graph
  3. Now you can turn the problem into finding the sum of the weights of the largest subtree in the tree
  4. As shown in the figure, 5 + 4 + (- 2) + 1 = 8 is the answer to the input data

step

  1. Input data and store the two endpoints of an edge in the adjacency table
  2. Recursively find the points that have edges with the current node, and then add the weight sum * * (greater than 0) of the child node to the weight sum of w[root] the current node. Update ans every time, and then we can know that when the root node of the tree is 1, the maximum weight sum in his subtree is ans, which is the solution of the problem**

be careful

The method of using adjacency table in Java. ArrayList < integer > [] g = new ArrayList [n + 1] in Java and vector < int > a [100] in cpp are very practical 👌

When the number of nodes in the graph is very large, using the adjacency table can effectively prevent the development space from being too large, resulting in memory overrun
In addition, this identical code can't pass with Java
http://oj.ecustacm.cn/problem.php?id=1262
However, cpp is OK, and it is said that due to the language characteristics, the Java version can only get 50% points when submitted to the Blue Bridge Cup official website, while cpp can get full marks. astonishing 🤧

code

/*
 * @Author: motongxue
 * @Date: 2020-10-14 16:35:43
 * @LastEditors: motongxue
 * @LastEditTime: 2020-10-14 18:33:57
 * @Blog: https://motongxue.cn
 * @Description: 2015 Java group B question 10 tree of life
 * Recursion from rootless tree to rooted tree
 */

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int n;
    static Long ans = 0L;
    static Long[] w;
    static ArrayList<Integer>[] g;  
    // ArrayList < integer > [] g = new ArrayList [n + 1] in Java 
    // Vector < int > a [100] used in cpp

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        w = new Long[n + 1];
        int x, y;
        g = new ArrayList[n + 1];
        for (int i = 0; i < n; i++) {
            w[i + 1] = sc.nextLong();    // read in data
            g[i+1] = new ArrayList<>();  // initialization
        }
        for (int i = 1; i < n; i++) {
            x = sc.nextInt();
            y = sc.nextInt();
            g[x].add(y);                // Connect the two ends of the edge
            g[y].add(x);
        }
        dfs(1, -1);                     // Consider 1 as the root node of the tree without parent node
        System.out.println(ans);
    }
    /**
     * root The subtree represented by the root has a maximum weight sum, which is stored in w[root]
     * @param root  Node at this time
     * @param fa    root Parent node of node
     */
    private static void dfs(int root, int fa) {
        for (int i = 0; i < g[root].size(); i++) {  //Traverse the points connected to root
            Integer child = g[root].get(i);
            if (child == fa)    // If we judge whether the child node is the father node. Prevent entry into dead cycle 1 - > 2 - > 1
                continue;
            dfs(child, root);   // Recursion of child nodes
            if (w[child] > 0)   // If the weight sum of the child node and its subtree is greater than zero, it can be added to the weight of the parent node
                w[root] += w[child];
        }
        ans = Math.max(ans, w[root]);   // Update ans every time
    }
}
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL ans = 0L;
LL w[N];
vector<int> g[N];
// ArrayList < integer > [] g = new ArrayList [n + 1] in Java
// Vector < int > a [100] used in cpp

/**
 * root The subtree represented by the root has a maximum weight sum, which is stored in w[root]
 * @param root  Node at this time
 * @param fa    root Parent node of node
 */
void dfs(int root, int fa)
{
    for (int i = 0; i < g[root].size(); i++)
    { //Traverse the points connected to root
        int child = g[root][i];
        if (child == fa) // If we judge whether the child node is the father node. Prevent entry into dead cycle 1 - > 2 - > 1
            continue;
        dfs(child, root); // Recursion of child nodes
        if (w[child] > 0) // If the weight sum of the child node and its subtree is greater than zero, it can be added to the weight of the parent node
            w[root] += w[child];
    }
    ans = max(ans, w[root]); // Update ans every time
}
int main()
{
    scanf("%d", &n);
    int x, y;
    for (int i = 0; i < n; i++)
        scanf("%lld", &w[i + 1]);

    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &x, &y);
        g[x].push_back(y); // Connect the two ends of the edge
        g[y].push_back(x);
    }
    dfs(1, -1); // Consider 1 as the root node of the tree without parent node
    printf("%lld\n", ans);
}

last

In fact, this is a tree DP topic. Is it OK to understand? I didn't expect to be able to write a topic of tree dynamic programming. Great 😂
Tree DP is also a kind of topic in dynamic programming. Let's introduce it here first. If you are interested, please pay attention to me 👏

October 14, 2020

Everyone thinks that writing is OK. You can praise, collect and pay attention to it!
You can also come to mine Personal blog Visit, it is estimated that it will be updated in recent years! Be friends with me! https://motongxue.cn

Tags: Dynamic Programming Graph Theory dfs

Posted by 2705ap on Thu, 12 May 2022 01:45:03 +0300