#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];
int depth[100009];
int dfs1(int v){
subsz[v] = 1;
for(auto u : g[v]){
prt[u] = v;
depth[u] = depth[v]+1;
dfs1(u);
subsz[v] += subsz[u];
}
}
int eul[100009];
int chain[100009];
ll cureul = 0;
int 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);
}
deque<pll> vec[100009];
ll bit[100009];
void updbit(ll idx, ll val){
++idx;
while(idx <= n+5){
bit[idx] += val;
idx += idx&(-idx);
}
}
ll getbit(ll idx){
++idx;
ll ret = 0;
while(idx > 0){
ret += bit[idx];
idx -= idx&(-idx);
}
return ret;
}
ll gettree(ll idx){
ll ret = 0;
vector<ll> erase;
while(idx != 0){
deque<pll> &v = vec[chain[idx]];
auto it = upper_bound(v.begin(), v.end(), mp(idx,ll(1e9)));
if(it == v.end())--it;
while(1){
int bef = depth[chain[idx]]-1;
if(it != v.begin())
bef = depth[(*(it-1)).ff];
int cnt = min(depth[idx], depth[(*it).ff])-bef;
//cout << (*it).ff << ' ' << chain[idx] << ' ' << bef << '\n';
ret += cnt*getbit((*it).ss-1);
updbit((*it).ss, cnt);
erase.pb((*it).ss);
if(it == v.begin()) break;
--it;
}
idx = prt[chain[idx]];
}
for(auto u : erase)
updbit(u, -(getbit(u)-getbit(u-1)));
return ret;
}
void updtree(ll idx, ll val){
while(idx != 0){
deque<pll> &v = vec[chain[idx]];
auto it = upper_bound(v.begin(), v.end(), mp(idx,ll(1e9)));
while(it != v.begin())
v.pop_front();
v.push_front({idx, val});
idx = prt[chain[idx]];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
vector<ll> compress;
for(int i = 1; i <= n; ++i){
cin >> val[i];
compress.pb(val[i]);
}
sort(compress.begin(), compress.end());
compress.resize(unique(compress.begin(), compress.end())-compress.begin());
for(int i = 1; i <= n; ++i)
val[i] = lower_bound(compress.begin(), compress.end(), val[i])-compress.begin();
for(int i = 1; i < n; ++i){
int x, y;
cin >> x >> y;
g[x].pb(y);
querry.pb(y);
}
dfs1(1);
dfs2(1);
updtree(1, val[1]);
for(auto u : querry){
cout << gettree(prt[u]) << '\n';
assert(getbit(n+1) == 0);
updtree(u, val[u]);
}
}
Compilation message
construction.cpp: In function 'int dfs1(int)':
construction.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
construction.cpp: In function 'int dfs2(int)':
construction.cpp:51:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
70136 KB |
Output is correct |
| 2 |
Correct |
56 ms |
70008 KB |
Output is correct |
| 3 |
Incorrect |
60 ms |
70008 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
70136 KB |
Output is correct |
| 2 |
Correct |
56 ms |
70008 KB |
Output is correct |
| 3 |
Incorrect |
60 ms |
70008 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
70136 KB |
Output is correct |
| 2 |
Correct |
56 ms |
70008 KB |
Output is correct |
| 3 |
Incorrect |
60 ms |
70008 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
