//
// Created by bvd on 5/26/20.
//
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int inf = (int) 1e9;
struct Result {
vector<pii> values;
ll inv;
bool isNil;
};
const Result nil = {vector<pii>(), 0, true};
map<int,int> M;
Result merge(Result a,Result b) {
if (a.isNil) return b;
if (b.isNil) return a;
//cerr << "a\n"; print(a); cerr << "b\n"; print(b);
M.clear();
for(auto& i: a.values) M[i.X]+=i.Y;
for(auto& i: b.values) M[i.X]+=i.Y;
Result res;
res.values.clear();
for (auto it=M.begin(); it!=M.end(); it++)
res.values.pb({(*it).X,(*it).Y});
int n = sz(a.values), m = sz(b.values);
vi fa; fa.resize(n);
fa[n-1] = a.values[n-1].Y;
for (int i=n-2; i>=0; i--)
fa[i] = fa[i+1]+a.values[i].Y;
int aptr = 0;
res.inv = a.inv+b.inv;
rep(bptr,0,m) {
while (aptr < n and a.values[aptr].X<=b.values[bptr].X) aptr++;
if (aptr==n) break;
res.inv+=(ll) fa[aptr]*(ll) b.values[bptr].Y;
}
res.isNil = false;
//cerr << "res\n"; print(res);
//cerr << '\n';
return res;
}
struct Node {
static const int maxn = 100000;
Node *l = 0, *r = 0;
int lo, hi;
bool lazy;
int lazyValue;
Result val;
Node(int lo,int hi): lo(lo), hi(hi) { lazy = false; lazyValue = 0; val = nil;}
Node(vi& v, int lo, int hi) : lo(lo), hi(hi) {
lazy = false;
lazyValue = 0;
//cerr << lo << ' ' << hi << endl;
if (lo + 1 < hi) {
int mid = lo + (hi - lo)/2;
l = new Node(v, lo, mid); r = new Node(v, mid, hi);
val = merge(l->val, r->val);
}
else val = { {{v[lo], 1}}, 0, false};
}
void print(Result a) {
cerr << "values\n";
for (auto i: a.values) cerr << i.X << ' ' << i.Y << '\n';
cerr << "inv "; cerr << a.inv << '\n';
cerr << "isNil "; cerr << a.isNil << '\n';
}
Result query(int L,int R) {
if (R <=lo || hi<=L) return nil;
if (L <=lo && hi<=R) return val;
push();
return merge(l->query(L,R), r->query(L,R));
}
void set(int L,int R,int x) {
if (R<=lo || hi<=L) return;
if (L<=lo && hi<=R) {
val = { {{x,hi-lo}}, 0, false } ;
lazy = true;
lazyValue = x;
return;
}
push(); l->set(L,R,x); r->set(L,R,x);
val = merge(l->val, r->val);
}
void push() {
if (!l) {
int mid = lo + (hi-lo)/2;
l = new Node(lo, mid); r = new Node(mid, hi);
}
if (lazy) {
l->set(lo,hi,lazyValue), r->set(lo,hi,lazyValue);
val.values = {{lazyValue, hi-lo}};
val.inv = 0;
val.isNil = false;
lazy = false;
}
}
};
template <bool VALS_EDGES> struct HLD {
int N, tim = 0;
vector<vi> adj;
vi par, siz, depth, rt, pos;
Node *tree;
HLD(vector<vi> adj_, vi& c)
: N(sz(adj_)), adj(adj_), par(N, -1), siz(N, 1), depth(N),
rt(N),pos(N) {
dfsSz();
dfsHld();
vi invpos; invpos.resize(N);
rep(i,0,N) invpos[pos[i]] = i;
vi nc; nc.resize(N);
rep(i,0,N) nc[invpos[i]] = c[i];
tree = new Node(nc,0,N);
}
void dfsSz(int v = 0) {
if (par[v] != -1) adj[v].erase(find(all(adj[v]), par[v]));
for (int& u : adj[v]) {
par[u] = v, depth[u] = depth[v] + 1;
dfsSz(u);
siz[v] += siz[u];
if (siz[u] > siz[adj[v][0]]) swap(u, adj[v][0]);
}
}
void dfsHld(int v = 0) {
pos[v] = tim++;
for (int u : adj[v]) {
rt[u] = (u == adj[v][0] ? rt[v] : u);
dfsHld(u);
}
}
template <class B> void process(int u, int v, B op) {
int prev = -1;
for (; rt[u] != rt[v]; v = par[rt[v]]) {
if (depth[rt[u]] > depth[rt[v]]) { assert(false); swap(u, v); }
assert(pos[rt[v]]!=prev);
op(pos[rt[v]], pos[v] + 1);
prev = pos[v] + 1;
}
if (depth[u] > depth[v]) {assert(false); swap(u, v); }
assert(pos[u] + VALS_EDGES!=prev);
op(pos[u] + VALS_EDGES, pos[v] + 1);
}
/*void modifyPath(int u, int v, int val) {
process(u, v, [&](int l, int r) { tree->add(l, r, val); });
}*/
void updatePath(int u,int v,int value) {
process(u, v, [&](int l, int r) {
tree->set(l, r, value);
});
}
Result queryPath(int u,int v) {
Result res = {vector<pii>(), 0, true};
process(u,v,[&](int l,int r) {
res = merge(tree->query(l,r), res);
});
return res;
}
/*int queryPath(int u, int v) { // Modify depending on query
int res = -1e9;
process(u, v, [&](int l, int r) {
res = max(res, tree->query(l, r));
});
return res;
}*/
/*int querySubtree(int v) { // modifySubtree is similar
return tree->query(pos[v] + VALS_EDGES, pos[v] + siz[v]);
}*/
};
const int maxn = 100000;
int n;
vi c;
int a[maxn+1], b[maxn+1];
vector<vi> G;
main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//freopen("debug.txt","w",stderr);
cin >> n;
rep(i,0,n) { int x; cin >> x; c.pb(x); }
G.resize(n);
rep(i,0,n-1) {
int u,v; cin >> u >> v; u--; v--; G[u].pb(v); G[v].pb(u);
a[i] = u, b[i] = v;
}
HLD<false> hld = HLD<false>(G,c);
rep(i,0,n-1) {
Result res = hld.queryPath(0, a[i]);
cout << res.inv << '\n';
hld.updatePath(0, a[i], c[b[i]]);
//res = hld.queryPath(0,a[i]);
//cerr << "assert " << a[i] << ' ' << b[i] << ' ' << c[b[i]] << ' ' << sz(res.values) << ' ' << res.values[0].X << ' ' << res.values[0].Y << '\n';
}
return 0;
}
Compilation message
construction.cpp:208:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
