fork(1) download
copy 
  1. /////////////////////////   _LeMur_
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <cassert>
  6. #include <bitset>
  7. #include <cstdio>
  8. #include <vector>
  9. #include <string>
  10. #include <ctime>
  11. #include <stack>
  12. #include <queue>
  13. #include <cmath>
  14. #include <ctime>
  15. #include <list>
  16. #include <map>
  17. #include <set>
  18.  
  19. using namespace std;
  20.  
  21. const int N = 100005;
  22. const int inf = 1000 * 1000 * 1000;
  23. const int mod = 998244353;
  24.  
  25. int n;
  26. int a[N];
  27.  
  28. vector < pair<int,int> > g[N];
  29. bool used[N];
  30.  
  31. int order[N] , nn;
  32.  
  33. long long dp[N] , fin[N];
  34. long long DP[N] , mn[N];
  35.  
  36. void rec(int v,int p){
  37.     ++nn;
  38.     order[v] = 1;
  39.     dp[v] = fin[v] = 0;
  40.     DP[v] = mn[v] = 0;
  41.     for(int i=0;i<(int)g[v].size();i++){
  42.         int to = g[v][i].first;
  43.         if(to == p || used[to])continue;
  44.         rec(to , v);
  45.         order[v] += order[to];
  46.     }
  47. }
  48.  
  49. int mnn , gag;
  50.  
  51. vector < long long > G;
  52.  
  53. void dfs(int v,int p){
  54.     int mx = nn - order[v];
  55.     for(int i=0;i<(int)g[v].size();i++){
  56.         int to = g[v][i].first;
  57.         int len = g[v][i].second;
  58.         if(to == p || used[to])continue;
  59.         dfs(to , v);
  60.         mx = max(mx , order[to]);
  61.     }
  62.     if(mx < mnn){
  63.         mnn = mx;
  64.         gag = v;
  65.     }
  66. }
  67.  
  68. void made(int v,int p){
  69.     order[v] = 1;
  70.     for(int i=0;i<(int)g[v].size();i++){
  71.         int to = g[v][i].first;
  72.         int len = g[v][i].second;
  73.         if(to == p || used[to])continue;
  74.         ///
  75.         fin[to] = fin[v] + a[v] - len;
  76.         dp[to] = dp[v];
  77.         if(fin[to] < 0){
  78.             dp[to] -= fin[to];
  79.             fin[to] = 0;
  80.         }
  81.         ///
  82.         int delta = a[to] - len;
  83.         DP[to] = DP[v] + delta;
  84.         mn[to] = min(1ll * delta , mn[v] + delta);
  85.         ///
  86.         made(to , v);
  87.         order[v] += order[to];
  88.     }
  89.     if(mn[v] >= 0){
  90.         G.push_back(DP[v]);
  91.     }
  92. }
  93.  
  94. int findcenter(int v){
  95.     nn = 0;
  96.     rec(v , -1);
  97.     mnn = inf;
  98.     dfs(v , -1);
  99.     made(gag , -1);
  100.     return gag;
  101. }
  102.  
  103. long long answ = 0;
  104. map < long long,int > mp;
  105.  
  106. vector < long long > P;
  107. vector <int> vert;
  108.  
  109. void solve(int v,int p){
  110.     if(p != -1){
  111.         vert.push_back(v);
  112.         if(mn[v] >= 0){
  113.             P.push_back(DP[v]);
  114.         }
  115.     }
  116.     int id = lower_bound(G.begin() , G.end() , dp[v]) - G.begin();
  117.     answ += (int)G.size() - id;
  118.     if(p == -1) answ--;
  119.     ///
  120.     for(int i=0;i<(int)g[v].size();i++){
  121.         int to = g[v][i].first;
  122.         if(to == p || used[to])continue;
  123.         solve(to , v);
  124.         if(p == -1){
  125.             sort(P.begin() , P.end());
  126.             for(int j=0;j<(int)vert.size();j++){
  127.                 int gag = vert[j];
  128.                 int id = lower_bound(P.begin() , P.end() , dp[gag]) - P.begin();
  129.                 answ -= (int)P.size() - id;
  130.             }
  131.             P.clear();
  132.             vert.clear();
  133.         }
  134.     }
  135. }
  136.  
  137. void centroid(){
  138.     queue <int> q;
  139.     q.push(1);
  140.     while(!q.empty()){
  141.         int v = q.front();
  142.         q.pop();
  143.         v = findcenter(v);
  144.         ///
  145.         sort(G.begin() , G.end());
  146.         solve(v , -1);
  147.         G.clear();
  148.         ///
  149.         for(int i=0;i<(int)g[v].size();i++){
  150.             int to = g[v][i].first;
  151.             if(order[to] == 1 || used[to])continue;
  152.             q.push(to);
  153.         }
  154.         used[v] = true;
  155.     }
  156. }
  157.  
  158. int main(){
  159.     scanf("%d",&n);
  160.     for(int i=1;i<=n;i++){
  161.         scanf("%d",&a[i]);
  162.     }
  163.     for(int i=1;i<n;i++){
  164.         int a , b , c;
  165.         scanf("%d%d%d",&a,&b,&c);
  166.         g[a].push_back(make_pair(b , c));
  167.         g[b].push_back(make_pair(a , c));
  168.     }
  169.     centroid();
  170.     cout<<answ<<endl;
  171.     return 0;
  172. }
Success #stdin #stdout 0s 21592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/BCQLER
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!