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 <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int LL;
const int N = 1e5+5;
const int M = 1e4+5;
const int INF = 0x3f3f3f3f;
int n,fa[N],rt;
vector<int>g[N];
LL mx[N],ret,ans,a[N];
void dfs(int u){
  mx[u]=a[u];
  for(int i=0;i<g[u].size();++i){
     int v = g[u][i];
     dfs(v);
     mx[u] = max(mx[u],a[u]+mx[v]);
  }
  ret = max(ret,mx[u]);
}
void solve(int u, LL w){
 //  printf("%d %lld\n",u,w);
   if(w+mx[u]<ret){
      LL ad =ret-w-mx[u];
      a[u] += ad;
      ans += ad;
   }
   w += a[u];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX