fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. // find_by_order, order_of_key
  8. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
  9. typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> omset;
  10. #define int long long
  11. #define endl '\n'
  12. #define pi pair<int,int>
  13. #define adjs(name, type, size) vector<vector<type>>name(size)
  14. #define adjpass(name, type) vector<vector<type>>&name
  15. #define rest(name, val) memset(name,val,sizeof(name))
  16. #define all(x) x.begin(),x.end()
  17. #define killua ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
  18. //changes in dir:
  19. int dx[] = {0, 0, 1, -1, -1, 1, -1, 1};
  20. int dy[] = {1, -1, 0, 0, 1, 1, -1, -1};
  21. int cases = 0;
  22.  
  23. /***إِلا أَنْ يَشَاءَ اللَّهُ وَاذْكُرْ رَبَّكَ إِذَا نَسِيتَ وَقُلْ عَسَى أَنْ يَهْدِيَنِي رَبِّي لأَقْرَبَ مِنْ هَذَا رَشَدًا ***/
  24. const int N = 1e5 + 5;
  25. int a[N], ans[N]; // 1 , -1
  26. vector<int> adj[N];
  27. int n, m;
  28.  
  29. map<int, int> dfs(int node, int p) {
  30.     int num = 1;
  31.     map<int, int> temp;
  32.     int st = 0;
  33.     for (auto child: adj[node]) {
  34.         if (child == p)continue;
  35.         map<int, int> k = dfs(child, node);
  36.         st = 1;
  37.         for (auto [x, y]: k) {
  38.             int nx = x + a[node];
  39.             temp[nx] += y;
  40.         }
  41.     }
  42.     temp[a[node]]++;
  43.     ans[node] += temp[0];
  44.     return temp;
  45. }
  46.  
  47. void gon() {
  48.     cin >> n >> m;
  49.     for (int i = 0; i < n; i++)cin >> a[i], (a[i] == 0 ? a[i] = -1 : a[i] = 1);
  50.     for (int i = 0; i < n - 1; i++) {
  51.         int u, v;
  52.         cin >> u >> v;
  53.         u--;
  54.         v--;
  55.         adj[u].push_back(v);
  56.         adj[v].push_back(u);
  57.     }
  58.     dfs(0, -1);
  59.     while (m--) {
  60.         int k;
  61.         cin >> k;
  62.         k--;
  63.         cout << ans[k] << endl;
  64.     }
  65. }
  66.  
  67. int32_t main() {
  68. #ifndef ONLINE_JUDGE
  69.     freopen("Input.txt", "r", stdin);
  70.     freopen("Output.txt", "w", stdout);
  71. #endif
  72.     killua;
  73.     int t = 1;
  74.     if (cases) cin >> t;
  75.     while (t--) {
  76.         gon();
  77.     }
  78. }
Success #stdin #stdout 0.01s 6744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wbJX4Z
language:
C++14 (gcc 8.3)
created:
10 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!