1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<vector>
using namespace std;
struct Node{
    long value;
    vector<Node*> next;
    
    Node(long value) {
        this->value = value;
    }
};
long DFS(Node *cur, long & ans)
{
    long max_value = 0, count = 0;
    for(auto next:cur->next) {
        long value = DFS(next, ans);
        if(value > max_value) {
            ans += (value - max_value) * count;
            max_value = value;
            count++;
        } else {
            ans += max_value - value;
            count++;
        }
    }
    
    return max_value + cur->value;
}
int main()
{
    int N;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX