#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
int N;
vector<int> adj[MAXN+10];
int A[MAXN+10], B[MAXN+10];
int par[MAXN+10], sz[MAXN+10];
void dfs(int now)
{
sz[now]=1;
for(int nxt : adj[now])
{
dfs(nxt);
sz[now]+=sz[nxt];
}
}
int head[MAXN+10], dfn[MAXN+10], idfn[MAXN+10], cnt;
void hld(int now)
{
dfn[now]=++cnt;
idfn[dfn[now]]=now;
int heavy=0;
for(int nxt : adj[now])
{
if(sz[heavy]<sz[nxt]) heavy=nxt;
}
if(heavy==0) return;
head[heavy]=head[now];
hld(heavy);
for(int nxt : adj[now])
{
if(nxt==heavy) continue;
head[nxt]=nxt;
hld(nxt);
}
}
struct Data
{
int l, r, v;
};
vector<Data> V[MAXN+10];
vector<int> comp;
struct BIT
{
int tree[MAXN+10];
void init() { memset(tree, 0, sizeof(tree)); }
void update(int i, int x) { for(; i<=N; i+=(i&-i)) tree[i]+=x; }
int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bit;
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
for(int i=1; i<=N; i++) A[i]=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1;
for(int i=1; i<N; i++)
{
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
par[v]=u;
B[i]=v;
}
dfs(1);
head[1]=1;
hld(1);
//printf("DFN\n");
//for(int i=1; i<=N; i++) printf("%d ", dfn[i]); printf("\n");
V[1].push_back({1, 1, A[1]});
for(int i=1; i<N; i++)
{
int u=par[B[i]], v=B[i];
int now=v;
vector<pii> V2;
while(1)
{
vector<pii> VV;
while(!V[head[now]].empty() && V[head[now]].back().r<=dfn[now])
{
VV.push_back({V[head[now]].back().v, V[head[now]].back().r-V[head[now]].back().l+1});
V[head[now]].pop_back();
}
if(!V[head[now]].empty() && dfn[V[head[now]].back().l]<=dfn[now])
{
VV.push_back({V[head[now]].back().v, dfn[now]-V[head[now]].back().l+1});
V[head[now]].back().l=dfn[now]+1;
}
V[head[now]].push_back({dfn[head[now]], dfn[now], A[v]});
reverse(VV.begin(), VV.end());
for(auto it : VV) V2.push_back(it);
if(head[now]==1) break;
now=par[head[now]];
}
reverse(V2.begin(), V2.end());
bit.init();
ll ans=0;
//printf("V2 of %d %d is\n", u, v);
for(auto it : V2)
{
//printf("%d %d\n", it.first, it.second);
ans+=(ll)it.second*(bit.query(N)-bit.query(it.first));
bit.update(it.first, it.second);
}
printf("%lld\n", ans);
}
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:95:7: warning: unused variable 'u' [-Wunused-variable]
95 | int u=par[B[i]], v=B[i];
| ^
construction.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
69 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
construction.cpp:70:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
70 | for(int i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]);
| ~~~~~^~~~~~~~~~~~~
construction.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
79 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5504 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5504 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5504 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
