// author : thembululquaUwU
// 3.9.2024
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'
using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;
const int MaxN = 2e5 + 5;
const int mod = 1e9 + 7;
void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}
int n, par[MaxN], sz[MaxN];
vi badj[MaxN], f;
int dfs(int u, int p = -1){
sz[u] = 1;
for (int v : badj[u]) if (v != p && par[v] < -1) sz[u] += dfs(v, u);
return sz[u];
}
int get_cen(int u, int m, int p = -1){
for (int v : badj[u]) if (v != p && par[v] < -1 && sz[v] * 2 > m) return get_cen(v, m, u);
return u;
}
int root;
void cen(int u = 0, int p = -1){
u = get_cen(u, dfs(u)); par[u] = p; if (p == -1) root = u;
for (int v : badj[u]) if (par[v] < -1) cen(v, u);
}
vector <ii> pairs = {{6, 1}, {4, 3}, {4, 2}, {4, 1}, {2, 1}};
ll cnt[MaxN][8]; int sign[MaxN][8];
void rs(int u, int child, int val){ if (u == -1) return;
if (val < 0) if (par[u] != -1) rs(par[u], u, val);
if (val < 0) for (int i = 0; i < 8; ++ i) cnt[u][i] -= cnt[child][i];
for (auto [l, r] : pairs) cnt[u][l | r] += val * (cnt[u][l] * cnt[child][r] + cnt[child][l] * cnt[u][r]);
if (val > 0) for (int i = 0; i < 8; ++ i) cnt[u][i] += cnt[child][i];
if (val > 0) if (par[u] != -1) rs(par[u], u, val);
}
void add(int u, int t, int val){ t = 1 << t;
rs(par[u], u, -1); //if (val == -1) return;
for (auto [l, r] : pairs) if (r == t || l == t) cnt[u][l | r] -= sign[u][t] * cnt[u][l ^ r ^ t];
if (t == 2) cnt[u][7] -= sign[u][t] * cnt[u][5];
cnt[u][t] += val; if (val == 1) sign[u][t] = 1; else sign[u][t] = 0;
for (auto [l, r] : pairs) if (r == t || l == t) cnt[u][l | r] += sign[u][t] * cnt[u][l ^ r ^ t];
if (t == 2) cnt[u][7] += sign[u][t] * cnt[u][5]; rs(par[u], u, 1);
}
void init(int N, vi F, vi U, vi V, int Q){
for (int i = 0; i < N - 1; ++ i){
int u = U[i], v = V[i];
badj[u].pb(v); badj[v].pb(u);
}
for (int i = 0; i < N; ++ i) par[i] = -2; cen(); f = F;
//for (int i = 0; i < N; ++ i) cerr << i << ' ' << par[i] << endl;
for (int i = 0; i < N; ++ i) add(i, f[i], 1);
//add(0, f[0], 1);
//add(2, f[2], -1);
//for (int i = 0; i < N; ++ i){
//for (int j = 0; j < 8; ++ j) cout << cnt[i][j] << ' ';
//cout << endl;
//}
}
void change(int u, int t){
add(u, f[u], -1);
f[u] = t; add(u, f[u], 1);
}
ll num_tours(){ return cnt[root][7];}
void solve(){
int n; cin >> n; vi f(n); for (int i = 0; i < n; ++ i) cin >> f[i];
vi u(n - 1), v(n - 1); for (int i = 0; i < n - 1; ++ i) cin >> u[i] >> v[i];
int q; cin >> q; init(n, f, u, v, q);
cout << num_tours() << endl;
for (int i = 1; i <= q; ++ i){
int x, y; cin >> x >> y;
change(x, y); cout << num_tours() << endl;
}
}
int main(){
if (fopen("pqh.inp", "r")){
freopen("pqh.inp", "r", stdin);
freopen("pqh.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1; // cin >> t;
while (t --) solve();
return 0;
}
Compilation message
joitour.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
18 | void maxl(auto &a, auto b) {a = max(a, b);}
| ^~~~
joitour.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
18 | void maxl(auto &a, auto b) {a = max(a, b);}
| ^~~~
joitour.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | void minl(auto &a, auto b) {a = min(a, b);}
| ^~~~
joitour.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | void minl(auto &a, auto b) {a = min(a, b);}
| ^~~~
joitour.cpp: In function 'void add(int, int, int)':
joitour.cpp:59:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
59 | if (t == 2) cnt[u][7] += sign[u][t] * cnt[u][5]; rs(par[u], u, 1);
| ^~
joitour.cpp:59:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
59 | if (t == 2) cnt[u][7] += sign[u][t] * cnt[u][5]; rs(par[u], u, 1);
| ^~
joitour.cpp: In function 'void init(int, vi, vi, vi, int)':
joitour.cpp:67:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
67 | for (int i = 0; i < N; ++ i) par[i] = -2; cen(); f = F;
| ^~~
joitour.cpp:67:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
67 | for (int i = 0; i < N; ++ i) par[i] = -2; cen(); f = F;
| ^~~
joitour.cpp: In function 'int main()':
joitour.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | freopen("pqh.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
joitour.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen("pqh.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccwa89Wl.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQF7L8k.o:joitour.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
