Language: C++

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};
 
const int MX = 200005;
int in[MX], out[MX], k;
vector<int> to[MX];
void dfs(int v, int p=-1) {
  in[v] = k++;
  for (int u : to[v]) {
    if (u == p) continue;
    dfs(u,v);
  }
  out[v] = k;
}
 
vector<int> vs[MX];
 
ll c2(ll n) { return n*(n+1)/2;}
 
int main() {
  int n;
  cin >> n;
  vector<int> c(n);
  rep(i,n) cin >> c[i];
  rep(i,n-1) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  dfs(0);
  rep(i,n) vs[c[i]-1].push_back(i);
  ll tot = c2(n);
  BIT<int> d(n);
  rep(i,n) d.add(i,1);
  rep(i,n) {
    ll ans = tot;
    vector<int>& nvs = vs[i];
    sort(nvs.begin(), nvs.end(), [&](int a, int b) {
      return in[a] > in[b];
    });
    vector<P> history;
    for (int v : nvs) {
      int cnt = 1;
      for (int u : to[v]) {
        if (in[u] < in[v]) continue;
        int num = d.sum(in[u], out[u]);
        ans -= c2(num);
        cnt += num;
      }
      d.add(in[v], -cnt);
      history.emplace_back(in[v], cnt);
    }
    ans -= c2(d.sum(0,n));
    for (auto p : history) {
      d.add(p.first, p.second);
    }
    cout << ans << endl;
  }
  return 0;
}
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

const int MX = 200005;
int in[MX], out[MX], k;
vector<int> to[MX];
void dfs(int v, int p=-1) {
  in[v] = k++;
  for (int u : to[v]) {
    if (u == p) continue;
    dfs(u,v);
  }
  out[v] = k;
}

vector<int> vs[MX];

ll c2(ll n) { return n*(n+1)/2;}

int main() {
  int n;
  cin >> n;
  vector<int> c(n);
  rep(i,n) cin >> c[i];
  rep(i,n-1) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  dfs(0);
  rep(i,n) vs[c[i]-1].push_back(i);
  ll tot = c2(n);
  BIT<int> d(n);
  rep(i,n) d.add(i,1);
  rep(i,n) {
    ll ans = tot;
    vector<int>& nvs = vs[i];
    sort(nvs.begin(), nvs.end(), [&](int a, int b) {
      return in[a] > in[b];
    });
    vector<P> history;
    for (int v : nvs) {
      int cnt = 1;
      for (int u : to[v]) {
        if (in[u] < in[v]) continue;
        int num = d.sum(in[u], out[u]);
        ans -= c2(num);
        cnt += num;
      }
      d.add(in[v], -cnt);
      history.emplace_back(in[v], cnt);
    }
    ans -= c2(d.sum(0,n));
    for (auto p : history) {
      d.add(p.first, p.second);
    }
    cout << ans << endl;
  }
  return 0;
}
Submission Info

Compiler output:
a.cc:99:8: error: redefinition of 'struct BIT<T>'
   99 | struct BIT {
      |        ^~~
a.cc:10:8: note: previous definition of 'struct BIT<T>'
   10 | struct BIT {
      |        ^~~
a.cc:120:11: error: redefinition of 'const int MX'
  120 | const int MX = 200005;
      |           ^~
a.cc:31:11: note: 'const int MX' previously defined here
   31 | const int MX = 200005;
      |           ^~
a.cc:121:5: error: redefinition of 'int in [200005]'
  121 | int in[MX], out[MX], k;
      |     ^~
a.cc:32:5: note: 'int in [200005]' previously declared here
   32 | int in[MX], out[MX], k;
      |     ^~
a.cc:121:13: error: redefinition of 'int out [200005]'
  121 | int in[MX], out[MX], k;
      |             ^~~
a.cc:32:13: note: 'int out [200005]' previously declared here
   32 | int in[MX], out[MX], k;
      |             ^~~
a.cc:121:22: error: redefinition of 'int k'
  121 | int in[MX], out[MX], k;
      |                      ^
a.cc:32:22: note: 'int k' previously declared here
   32 | int in[MX], out[MX], k;
      |                      ^
a.cc:122:13: error: redefinition of 'std::vector<int> to [200005]'
  122 | vector<int> to[MX];
      |             ^~
a.cc:33:13: note: 'std::vector<int> to [200005]' previously declared here
   33 | vector<int> to[MX];
      |             ^~
a.cc:123:6: error: redefinition of 'void dfs(int, int)'
  123 | void dfs(int v, int p=-1) {
      |      ^~~
a.cc:34:6: note: 'void dfs(int, int)' previously defined here
   34 | void dfs(int v, int p=-1) {
      |      ^~~
a.cc:132:13: error: redefinition of 'std::vector<int> vs [200005]'
  132 | vector<int> vs[MX];
      |             ^~
a.cc:43:13: note: 'std::vector<int> vs [200005]' previously declared here
   43 | vector<int> vs[MX];
      |             ^~
a.cc:134:4: error: redefinition of 'll c2(ll)'
  134 | ll c2(ll n) { return n*(n+1)/2;}
      |    ^~
a.cc:45:4: note: 'll c2(ll)' previously defined here
   45 | ll c2(ll n) { return n*(n+1)/2;}
      |    ^~
a.cc:136:5: error: redefinition of 'int main()'
  136 | int main() {
      |     ^~~~
a.cc:47:5: note: 'int main()' previously defined here
   47 | int main() {
      |     ^~~~
a.cc:179:1: error: 'Submission' does not name a type
  179 | Submission Info
      | ^~~~~~~~~~