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 <bits/stdc++.h>
using namespace std;
enum{N = 100006, maxWallet = 200000004};
int p[N], q[N];
vector<int> g[N];
int cmp(int a, int b)
{
    return q[a] > q[b];
}
void dfs(int u, int pre)
{
    int minWallet = maxWallet;
    int wallet = maxWallet;
    vector<int> child;
    for(int i=0; i<g[u].size(); ++i)
    {
        int v = g[u][i];
        if (v == pre) continue;
        dfs(v, u);
        child.push_back(v);
    }
    
    wallet -= p[u];
    minWallet = min(minWallet, wallet);
    wallet += q[u];
    
    sort(child.begin(), child.end(), cmp);
    
    for (int i=0; i<child.size(); ++i)
    {
        int v = child[i];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX