#include "joitour.h"
#include <bits/stdc++.h>
using ll = long long ;
using ull = unsigned ll;
#define f first
#define s second
#define pb push_back
#define epb emplace_back
using namespace std;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
struct Data{
vector <ll> f[3];
int n;
vector <ll> cnt;
vector <vector<ll>>cnts;
Data() {
cnt.resize(5);
}
void add(int pos, int val, int id) {
while(pos < f[id].size()) {
f[id][pos] += val;
pos += (pos & -pos);
}
}
ll get(int pos, int id) {
ll res = 0;
while(pos) {
res += f[id][pos];
pos -= (pos & -pos);
}
return res;
}
ll get(int l, int r, int id) {
return get(r, id) - get(l - 1, id);
}
};
const int nmax = 200001;
vector <vector <int>>vec(nmax);
vector <vector <int>>sz(nmax);
vector <vector<int>>in(nmax);
vector <vector <int>>g(nmax);
vector <int>y(nmax);
vector <vector<int>>lead_in(nmax);
Data dt[nmax];
vector <bool> blocked(nmax);
vector <int> siz(nmax);
ll ans;
int timer = 1;
vector <vector<ll>>cnt(nmax, vector<ll>(5));
void dfs(int v, int e) {
// cout << v << ' ';
siz[v] = 1;
for(int to : g[v]) {
if(to == e || blocked[to]) continue;
dfs(to, v);
siz[v] += siz[to];
}
}
int find_cent(int v, int e, int n) {
for(int to : g[v]) {
if(blocked[to] || to == e) continue;
if(siz[to] * 2 >= n) return find_cent(to, v, n);
}
return v;
}
void clear_dfs(int v, int e) {
siz[v] = 0;
for(int to : g[v]) {
if(to == e || blocked[to]) continue;
clear_dfs(to, v);
}
siz[v] = 0;
}
void update_cnt(int v, int to, bool x = false) {
for(int i = 0; i < 5; i++) cnt[v][i] += cnt[to][i];
if(y[v] == 1 && !x) {
cnt[v][3] += cnt[to][0];
cnt[v][4] += cnt[to][2];
}
}
void DFS(int v, int e, int num, vector<int>&visited) {
in[v].pb(timer++);
lead_in[v].pb(num);
sz[v].pb(1);
visited.pb(v);
for(int j = 0; j < 5; j++) cnt[v][j] = 0;
for(int to : g[v]) {
if(to == e || blocked[to]) continue;
DFS(to, v, num, visited);
update_cnt(v, to);
}
cnt[v][y[v]]++;
}
void clearDFS(int v, int e) {
cnt[v].assign(5, 0);
for(int to : g[v]) {
if(to == e || blocked[to]) continue;
clearDFS(to, v);
}
}
void decompose(int v) {
dfs(v, v);
int n = siz[v];
int x = find_cent(v, v, siz[v]);
clear_dfs(v, v);
timer = 1;
sz[x].pb(n);
int num = 0;
vector <int> visited;
for(int to : g[x]) {
if(blocked[to]) continue;
DFS(to, x, num, visited);
update_cnt(x, to, true);
dt[x].cnts.pb(cnt[to]);
num++;
}
cnt[x][y[x]]++;
for(int j = 0; j< 3; j++) {
dt[x].f[j].resize(n + 1);
}
dt[x].cnt = cnt[x];
for(auto to : visited) {
if(y[to] != 1) {
dt[x].add(in[to].back(), 1, y[to]);
}
}
clearDFS(x, x);
timer = 1;
blocked[x] = true;
for(int to : g[x]) {
if(!blocked[to]) decompose(to);
}
}
void init(int n, std::vector<int> f, std::vector<int> u, std::vector<int> v,int q) {
for(int i = 0; i < f.size(); i++) {
y[i] = f[i];
}
// cout << 1;
for(int i = 0; i < u.size(); i++) {
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
// cout << 1;
decompose(0);
// cout << 1;
for(int i = 0; i < n; i++) {
for(auto to : dt[i].cnts) {
ans += (dt[i].cnt[0] - to[0]) * to[4] + (dt[i].cnt[2] - to[2]) * to[3] + to[0] * (dt[i].cnt[4] - to[4]) + to[2] * (dt[i].cnt[3] - to[3]);
if(y[i] == 1) {
ans += to[2] * (dt[i].cnt[0] - to[0]) + to[0] * (dt[i].cnt[2] - to[2]);
}
}
// cout << ans << ' ';
}
}
void change(int X, int Y) {}
long long num_tours() {
return ans / 2;
}
