#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n;
vector<int> querry;
int val[100009];
vector<int> g[100009];
int prt[100009];
int subsz[100009];
void dfs1(int v){
subsz[v] = 1;
for(auto u : g[v]){
prt[u] = v;
dfs1(u);
subsz[v] += subsz[u];
}
}
int eul[100009];
int chain[100009];
int cureul = 0;
void dfs2(int v){
//cout << v << " -- " << cureul << '\n';
eul[v] = cureul++;
if(eul[prt[v]] == eul[v]-1)
chain[v] = chain[prt[v]];
else
chain[v] = v;
int biggest = 0, id = 0;
for(auto u : g[v])
if(subsz[u] > biggest){
biggest = subsz[u];
id = u;
}
if(id != 0)
dfs2(id);
for(auto u : g[v])
if(u != id)
dfs2(u);
}
struct node{
unordered_map<int, int> mpp;
int ret = 0;
};
node merge(node n1, node n2){
node n = node();
n.ret = n1.ret+n2.ret;
auto it = n2.mpp.begin();
int cur = 0;
for(auto u : n1.mpp){
while(it != n2.mpp.end() && (*it).ff < u.ff){
cur += (*it).ss;
++it;
}
n.ret += cur*u.ss;
}
for(auto u : n1.mpp)
n.mpp[u.ff] += u.ss;
for(auto u : n2.mpp)
n.mpp[u.ff] += u.ss;
return n;
}
void mergeref(node &n1, node &n2, node &n){
n.ret = n1.ret+n2.ret;
n.mpp.clear();
auto it = n2.mpp.begin();
int cur = 0;
for(auto u : n1.mpp){
while(it != n2.mpp.end() && (*it).ff < u.ff){
cur += (*it).ss;
++it;
}
n.ret += cur*u.ss;
}
for(auto u : n1.mpp)
n.mpp[u.ff] += u.ss;
for(auto u : n2.mpp)
n.mpp[u.ff] += u.ss;
}
node seg[400009];
int lazy[400009];
void push(int v, int tl, int tm, int tr){
if(lazy[v] == 0) return;
seg[2*v].ret = seg[2*v+1].ret = 0;
seg[2*v].mpp.clear();
seg[2*v+1].mpp.clear();
seg[2*v].mpp[lazy[v]] = (tm-tl+1);
seg[2*v+1].mpp[lazy[v]] = (tr-tm);
lazy[2*v] = lazy[2*v+1] = lazy[v];
lazy[v] = 0;
}
node get(int v, int tl, int tr, int l, int r){
if(r < tl || tr < l)
return node();
if(l <= tl && tr <= r)
return seg[v];
else{
int tm = (tl+tr)/2;
push(v, tl, tm, tr);
return merge(get(2*v, tl, tm, l, r), get(2*v+1, tm+1, tr, l, r));
}
}
void upd(int v, int tl, int tr, int l, int r, int val){
if(r < tl || tr < l)
return;
if(l <= tl && tr <= r){
lazy[v] = val;
seg[v].ret = 0;
seg[v].mpp.clear();
seg[v].mpp[val] = (tr-tl+1);
}
else{
int tm = (tl+tr)/2;
push(v, tl, tm, tr);
upd(2*v, tl, tm, l, r, val);
upd(2*v+1, tm+1, tr, l, r, val);
mergeref(seg[2*v], seg[2*v+1], seg[v]);
}
}
int gettree(int idx){
node cur = node();
while(idx != 0){
cur = merge( get(1, 0, n-1, eul[chain[idx]], eul[idx]) ,cur);
idx = prt[chain[idx]];
}
return cur.ret;
}
void updtree(int idx, int val){
while(idx != 0){
upd(1, 0, n-1, eul[chain[idx]], eul[idx], val);
idx = prt[chain[idx]];
}
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
cin >> val[i];
for(int i = 1; i < n; ++i){
int x, y;
scanf("%d%d", &x, &y);
g[x].pb(y);
querry.pb(y);
}
dfs1(1);
dfs2(1);
for(auto u : querry){
printf("%d\n", gettree(u));
updtree(u, val[u]);
}
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:151:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
construction.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 2 |
Correct |
23 ms |
27768 KB |
Output is correct |
| 3 |
Incorrect |
25 ms |
27640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 2 |
Correct |
23 ms |
27768 KB |
Output is correct |
| 3 |
Incorrect |
25 ms |
27640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
27768 KB |
Output is correct |
| 2 |
Correct |
23 ms |
27768 KB |
Output is correct |
| 3 |
Incorrect |
25 ms |
27640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
