fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define Hoshimachi signed
  3. #define Suisei main
  4. using namespace std;
  5. #define int long long
  6. #define tup tuple<int,int,int>
  7. const int N=2e5+5,mod=1e9+7;
  8. // nho reset
  9. int n,t,a[N];
  10. vector<int> adj[N];
  11. int sz[N];
  12. bool vis[N],ok[N],del[N];
  13. void dfs_sz(int u, int par){
  14.     sz[u]=1;
  15.     vis[u]=1;
  16.     for(auto v:adj[u]){
  17.         if(v==par or !ok[v] or del[v]) continue;
  18.         dfs_sz(v,u);
  19.         sz[u]+=sz[v];
  20.     }
  21. }
  22. void dfssum(int u, int par, int k, int &s){
  23.     for(auto v:adj[u]){
  24.         if(v==par or !ok[v]) continue;
  25.         s+=sz[v]*(k-sz[v]);
  26.         dfssum(v,u,k,s);
  27.     }
  28. }
  29. void resetfull(){
  30.     for(int i=1; i<=n; i++){
  31.         sz[i]=0;
  32.         vis[i]=ok[i]=del[i]=0;
  33.     }
  34. }
  35. int Solve(int lim){
  36.     resetfull();
  37.     vector<int> st;
  38.     for(int i=1; i<=n; i++){
  39.         if(a[i]<=lim) ok[i]=1;
  40.         else ok[i]=0;
  41.     }
  42.     vector<vector<int>> tplt;
  43.     int ans=0;
  44.     for(int i=1; i<=n; i++){
  45.         if(ok[i] && !vis[i]){
  46.             dfs_sz(i,0);
  47.             int k=sz[i],s=0;
  48.             dfssum(i,0,k,s);
  49.             ans=(ans+(k-2)*s)%mod;
  50.         }
  51.     }
  52.     return ans;
  53. }
  54. Hoshimachi Suisei(){
  55.     ios_base::sync_with_stdio(0);
  56.     cin.tie(0); cout.tie(0);
  57.     // freopen(".inp", "r", stdin);
  58.     // freopen(".out", "w", stdout);
  59.     cin>>n>>t;
  60.     for(int i=1; i<=n; i++){
  61.         cin>>a[i];
  62.     }
  63.     for(int i=1; i<n; i++){
  64.         int u,v;
  65.         cin>>u>>v;
  66.         adj[u].push_back(v);
  67.         adj[v].push_back(u);
  68.     }
  69.     cout<<(Solve(t)-Solve(t-1)+mod)%mod;
  70. }
  71.  
Success #stdin #stdout 0.01s 8200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/40MXtU
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

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!