#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<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n;
vector<ll> querry;
ll val[100009];
vector<ll> g[100009];
ll prt[100009];
ll subsz[100009];
ll depth[100009];
ll dfs1(ll v){
subsz[v] = 1;
for(auto u : g[v]){
prt[u] = v;
depth[u] = depth[v]+1;
dfs1(u);
subsz[v] += subsz[u];
}
}
ll chain[100009];
ll dfs2(ll v){
//cout << v << " -- " << cureul << '\n';
if(chain[v] == 0)
chain[v] = v;
ll biggest = 0, id = 0;
for(auto u : g[v])
if(subsz[u] > biggest){
biggest = subsz[u];
id = u;
}
if(id != 0){
chain[id] = chain[v];
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){
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;
set<ll> erase;
while(idx != 0){
deque<pll> &v = vec[chain[idx]];
auto it = v.end();
--it;
while(1){
//if(it != v.begin() && depth[(*(it-1)).ff] >= depth[idx])
// --it;
ll bef = depth[chain[idx]]-1;
if(it != v.begin())
bef = depth[(*(it-1)).ff];
ll 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.insert((*it).ss);
if(it == v.begin()) break;
--it;
}
idx = prt[chain[idx]];
}
for(auto u : erase)
updbit(u, -(getbit(u)));
return ret;
}
void updtree(ll idx, ll val){
while(idx != 0){
deque<pll> &v = vec[chain[idx]];
while(!v.empty() && depth[v.front().ff] <= depth[idx])
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(ll 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(ll i = 1; i <= n; ++i)
val[i] = lower_bound(compress.begin(), compress.end(), val[i])-compress.begin();
for(ll i = 1; i < n; ++i){
ll 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';
for(int i = 1; i <= n; ++i)
assert(bit[i] == 0);
updtree(u, val[u]);
}
}
Compilation message
construction.cpp: In function 'll dfs1(ll)':
construction.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
construction.cpp: In function 'll dfs2(ll)':
construction.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
70008 KB |
Output is correct |
| 2 |
Correct |
53 ms |
70008 KB |
Output is correct |
| 3 |
Incorrect |
55 ms |
70008 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
70008 KB |
Output is correct |
| 2 |
Correct |
53 ms |
70008 KB |
Output is correct |
| 3 |
Incorrect |
55 ms |
70008 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
70008 KB |
Output is correct |
| 2 |
Correct |
53 ms |
70008 KB |
Output is correct |
| 3 |
Incorrect |
55 ms |
70008 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
