Subtree problem

Got any idea how to solve this problem?

Given a tree with n vertices v1,v2,...vn which is rooted at v1 . Each vertex has an integer on it.

For all subtrees, please calculate the sum of all integers on the vertices in the subtree.

Input Format

The first line is an integer n .

The next n line has numbers c1,~cn , where ci is the number on vertex vi for 1<=i<=n .

The following lines n-1 lines describe the edges on the tree. Each line has two integers a,b , meaning that there is an edge (va,vb) on the tree.

Output Format

Please output n numbers separated with space, where the i-th number is the sum of the integers on the vertices in the subtree rooted at vi.

Sample Input 0

5
4 8 7 6 3
1 2
3 5
4 1
1 3
Sample Output 0

28 8 10 6 3

deleted account xyzzy (5768)

So.....what is your attempt to solve this? Seeing some code would be nice.

DizzyDon (121)

What is the point of constantly asking lastchance to solve these problems for you?
It's ridiculous.

Pen72 (74)

Well I was trying to implement it with an adjacency list, then found it wasn't appropriate for this problem since it can't fully demonstrate parents and child relation, still have to build the tree according to the pairs first and am struggling searching the right method to build it, anyways will keep trying.

Last edited on

lastchance (6980)

#include <iostream>
#include <vector>
#include <set>
using namespace std;

//==========================================================

struct Node
{
   int sumSubTree = 0;
   int value;
   set<int> neighbours;      // children OR parents
};

//==========================================================

void sumSub( vector<Node> &nodes, set<int> &parents, int n )    // Recursively sum subtrees DOWNWARD
{
   nodes[n].sumSubTree = nodes[n].value;
   for ( int c : nodes[n].neighbours )
   {
      if ( parents.insert( c ).second )                         // Prevents going UP a generation
      {
         sumSub( nodes, parents, c );
         nodes[n].sumSubTree += nodes[c].sumSubTree;
      }
   }
}

//==========================================================

int main()
{
   // Read data
   int N;
   cin >> N;
   vector<Node> nodes(1+N);
   for ( int i = 1; i <= N; i++ ) cin >> nodes[i].value;
   for ( int i = 1; i <  N; i++ )
   {
      int a, b;
      cin >> a >> b;
      nodes[a].neighbours.insert( b );      // parent OR child
      nodes[b].neighbours.insert( a );      // ditto
   }

   // Recursively sum subtrees
   set<int> parents{ 1 };
   sumSub( nodes, parents, 1 );

   // Final results
   for ( int i = 1; i <= N; i++ ) cout << nodes[i].sumSubTree << ' ';
   cout << '\n';
}

28 8 10 6 3

Last edited on

Pen72 (74)

Can't quite understand line 20~25, does ( parents.insert( c ).second ) means the node's neighbor's value, so if it exists then will keep searching for more neighbors? And it shows a few wrong test cases when running code.

lastchance (6980)

The format of the input edges does not make it obvious which node is parent and which is child, as the edge may go either way. (There are examples of both ways in the given sample.) So the set<int> neighbours includes the parent of each node. This is not needed in the subtree sum so must be excluded. That is the purpose of parents.insert( c ).second. The insert function returns an {iterator,boolean} pair. If the boolean is false then the insert failed because the set already contains node c (because it is higher up the tree; i.e. the parent). You only need to sum over the subtrees of the children.

Pen72 wrote:
it shows a few wrong test cases

That's not particularly helpful information when it comes to debugging.
- what test data causes it to fail (and why)?
- does it fail all, most, or just one or two?
- does it give wrong answer, crash or blow the stack?
- did you have to amend the code in order to apply it in your tester?

Please state the whole problem - including any restrictions on the number of nodes and their values.

In case of overflowing an int variable you could try simply changing int sumSubTree = 0; to long long sumSubTree = 0; and see if that improves things. If the recursion is so extensive as to blow the call stack then one would need a rethink as to how to store the tree and compute the subtree sums.

A more complex tree has input file (you can redirect standard input):

13
10 20 30 40 50 60 70 80 90 100 110 120 130
1 4
13 1
4 6
4 8
11 4
13 12
2 12
12 10
13 3
12 9
7 3
1 5

This still gives the correct answer

910 20 100 290 50 60 70 80 90 100 110 330 560

Last edited on

Pen72 (74)

Thanks for the clear explanation. Also,yes it was overflow causing the problem.

Topic archived. No new replies allowed.