/// In The Name Of God
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ioi exit(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = (int)1e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;
int n;
int a[N];
pair <int, int> e[N];
vector <int> g[N];
int sz[N], up[N], par[N], len[N], dep[N];
inline void dfs_sz(int v = 1, int p = 0) {
sz[v]++;
par[v] = p;
dep[v] = dep[p] + 1;
for (auto &to : g[v]) {
if (to != p) {
dfs_sz(to, v);
sz[v] += sz[to];
if (sz[to] > sz[g[v][0]]) swap(g[v][0], to);
}
}
}
inline void dfs(int v = 1) {
len[up[v]]++;
for (auto to : g[v]) {
up[to] = (to == g[v][0] ? up[v] : to);
dfs(to);
}
}
vector < pair <int, int > > path[N];
inline void paint_v(vector < pair <int, int> > &x, int L, int c) {
reverse(all(x));
int add = L;
while (sz(x)) {
auto &it = x.back();
if (it.s <= L) {
L -= it.s;
x.pp();
}
else {
it.s -= L;
break;
}
}
x.pb({c, add});
reverse(all(x));
}
inline void paint(int v, int x) {
paint_v(path[up[v]], dep[v] - dep[up[v]] + 1, x);
v = par[up[v]];
while (v) {
int cut = dep[v] - dep[up[v]] + 1, L = cut;
reverse(all(path[up[v]]));
while (sz(path[up[v]])) {
auto &it = path[up[v]].back();
if (it.s <= cut) {
cut -= it.s;
path[up[v]].pp();
}
else {
it.s -= cut;
break;
}
}
path[up[v]].pb({x, L});
reverse(all(path[up[v]]));
v = par[up[v]];
}
}
vector < pair <int, int> > s;
pair <int, int> bfr[N], nbfr[N];
inline ll inv(int l, int r) {
if (l >= r) {
if (l == r) bfr[r] = s[r];
return 0;
}
int mid = (l + r) >> 1;
ll res = inv(l, mid) + inv(mid + 1, r), pref = 0;
int ptr = l, pos = l;
rep(i, mid + 1, r) {
while (ptr <= mid && bfr[ptr].f < bfr[i].f) {
pref += bfr[ptr].s;
nbfr[pos++] = bfr[ptr++];
}
nbfr[pos++] = bfr[i];
res += (ll)bfr[i].s * pref;
}
while (ptr < mid) nbfr[pos++] = bfr[ptr++];
rep(i, l, r) {
bfr[i] = nbfr[i];
}
return res;
}
inline void calc(int v, int u) {
s.clear();
int L = dep[v] - dep[up[v]] + 1, V = v;
for (auto it : path[up[v]]) {
if (it.s < L) {
if (sz(s) && s.back().f == it.f) {
s[sz(s) - 1].s += it.s;
}
else {
s.pb(it);
}
L -= it.s;
}
else {
if (sz(s) && s.back().f == it.f) {
s[sz(s) - 1].s += L;
}
else {
s.pb({it.f, L});
}
break;
}
}
reverse(all(s));
v = par[up[v]];
while (v) {
int need = dep[v] - dep[up[v]] + 1;
vector < pair <int, int > > add;
for (auto it : path[up[v]]) {
if (it.s < need) {
add.pb(it);
need -= it.s;
}
else {
add.pb({it.f, need});
break;
}
}
reverse(all(add));
for (auto it : add) {
if (sz(s) && s.back().f == it.f) {
s[sz(s) - 1].s += it.s;
}
else {
s.pb(it);
}
}
v = par[up[v]];
}
ll cnt = inv(0, sz(s) - 1);
/*
rep(i, 0, sz(s) - 1) {
rep(j, i + 1, sz(s) - 1) {
if (s[i].f > s[j].f) cnt += s[i].s * 1ll * s[j].s;
}
}*/
paint(V, a[u]);
if (sz(path[up[u]]) && path[up[u]].back().f == a[u]) {
path[up[u]][sz(path[up[u]]) - 1].s++;
}
else {
path[up[u]].pb({a[u], 1});
}
cout << cnt << nl;
}
int main() {
#ifdef IOI2018
freopen ("in.txt", "r", stdin);
freopen ("A.out", "w", stdout);
#endif
Kazakhstan
cin >> n;
rep(i, 1, n) cin >> a[i];
rep(i, 2, n) {
cin >> e[i].f >> e[i].s;
g[e[i].f].pb(e[i].s);
}
dfs_sz();
up[1] = 1;
dfs();
rep(i, 2, n) {
calc(e[i].f, e[i].s);
}
ioi
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
