#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1 << 17;
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N;
int A[MAXN], B[MAXN];
int C[MAXN];
vector<int> adj[MAXN];
int ent[MAXN], exi[MAXN];
struct segtree {
pii tree[2 * MAXN]; //pii(time, value)
void update (int x, pii v) {
tree[x += MAXN] = v;
while (x >>= 1) {
tree[x] = max(tree[2 * x], tree[2 * x + 1]);
}
}
pii query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
if (rt <= a || b <= lt) {
return pii(-1, -1);
}
if (a <= lt && rt <= b) {
return tree[cur];
}
int mid = (lt + rt) / 2;
return max(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt));
}
} seg;
void updpath (int x) {
static int updtime = 0;
seg.update(ent[x], pii(++updtime, C[x]));
}
int lastupd (int x) {
//last update of this one
return seg.query(ent[x], exi[x]).se;
}
void dfs (int x) {
static int cur = 0;
ent[x] = cur++;
for (int y : adj[x]) {
dfs(y);
}
exi[x] = cur;
updpath(x);
assert(lastupd(x) == C[x]);
}
struct node {
node *ch[2], *p;
int id;
int size;
} *null = new node, nodes[MAXN];
int getdir (node *n) {
if (n->p == null) {
return -1;
}
if (n == n->p->ch[0]) {
return 0;
}
if (n == n->p->ch[1]) {
return 1;
}
return -1;
}
bool isroot (node *n) {
return getdir(n) == -1;
}
void setc (node *n, node *c, int d) {
n->ch[d] = c;
if (c != null) {
c->p = n;
}
}
void pull (node *n) {
n->size = n->ch[0]->size + 1 + n->ch[1]->size;
}
void rot (node *n) {
node *p = n->p, *g = p->p;
bool d = getdir(n);
//note that this matters in an LCT. cannot cal setc on g and n
int pdir = getdir(p);
if (pdir != -1) {
g->ch[pdir] = n;
}
setc(p, n->ch[!d], d);
n->p = g; //this line forgot include...
setc(n, p, !d);
pull(p);
pull(n);
}
void splay (node *n) {
while (!isroot(n)) {
int pdir = getdir(p);
node *p = n->p;
if (pdir != -1) {
rot(getdir(n) == pdir ? n : p);
}
rot(n);
}
}
vector<pii> expose (node *u) {
//pii(size, value of node)
vector<pii> res;
int psize = 0;
for (node *cur = u, *v = null; cur != null; v = cur, cur = cur->p) {
splay(cur);
assert(v == null || v->p == cur);
cur->ch[1] = v;
pull(cur);
if (v != null) {
res.push_back(pii(lastupd(cur->id), cur->size - psize));
}
psize = cur->size;
}
splay(u);
return res;
}
struct fenwick {
ll bit[MAXN];
void update (int x, ll v) {
for (x++; x < MAXN; x += (x & -x)) {
bit[x] += v;
}
}
ll query (int x) {
ll res = 0;
for (x++; x; x &= (x - 1)) {
res += bit[x];
}
return res;
}
} fen;
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &C[i]);
}
//compress C
vector<int> vals(C, C + N);
sort(all(vals));
vals.resize(unique(all(vals)) - vals.begin());
for (int i = 0; i < N; i++) {
C[i] = lower_bound(all(vals), C[i]) - vals.begin();
}
for (int i = 0; i < N - 1; i++) {
scanf("%d %d", &A[i], &B[i]);
A[i]--;
B[i]--;
adj[A[i]].push_back(B[i]);
}
dfs(0);
//NOW THE NODES!
null->ch[0] = null->ch[1] = null->p = null;
null->id = -1073741819;
null->size = 0;
for (int i = 0; i < N; i++) {
nodes[i].ch[0] = nodes[i].ch[1] = nodes[i].p = null;
nodes[i].id = i;
nodes[i].size = 1;
}
for (int i = 0; i < N - 1; i++) {
nodes[B[i]].p = nodes + A[i];
}
for (int i = 0; i < N - 1; i++) {
int a = A[i], b = B[i];
vector<pii> v = expose(nodes + b);
//we want the number of strictly less than this value.
ll ans = 0;
for (pii p : v) {
ans += p.se * fen.query(p.fi - 1);
fen.update(p.fi, p.se);
}
for (pii p : v) {
fen.update(p.fi, -p.se);
}
printf("%lld\n", ans);
updpath(b);
}
}
Compilation message
construction.cpp: In function 'void splay(node*)':
construction.cpp:119:21: error: 'p' was not declared in this scope
int pdir = getdir(p);
^
construction.cpp: In function 'int main()':
construction.cpp:203:7: warning: unused variable 'a' [-Wunused-variable]
int a = A[i], b = B[i];
^
construction.cpp:167:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
construction.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &C[i]);
~~~~~^~~~~~~~~~~~~
construction.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &A[i], &B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
