This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#define FILE_IO
typedef pair<int, int> pii;
typedef long long LL;
const int NMAX = 1e5 + 5;
int N, K;
int v[NMAX], sz[NMAX], chn[NMAX], f[NMAX], pos[NMAX];
vector<int> nodes[NMAX], edg[NMAX];
vector<pii> edges, blk, aux, blocks[NMAX];
class Normalizer
{
public:
map<int, int> mp;
vector<int> ord;
void add(int x)
{
if(mp.count(x)) return;
mp[x]; ord.push_back(x);
}
int get(int x) { return mp[x]; }
void normalize()
{
sort(begin(ord), end(ord));
for(int i = 0; i < ord.size(); i++)
mp[ ord[i] ] = i + 1;
}
}nrm;
class BinaryIndexedTree
{
public:
vector<int> aib;
void init(int N)
{
aib.resize(N + 5);
}
void U(int pos, int val)
{
for(; pos < aib.size(); pos += (pos & (-pos)))
aib[pos] += val;
}
int Q(int pos)
{
int ans = 0;
for(; pos > 0; pos -= (pos & (-pos)))
ans += aib[pos];
return ans;
}
}aib;
void DFS(int nod, int fth = 0)
{
sz[nod] = 1;
f[nod] = fth;
for(auto &nxt: edg[nod])
{
DFS(nxt, nod);
sz[nod] += sz[nxt];
if(sz[nxt] > sz[ edg[nod][0] ]) swap(nxt, edg[nod][0]);
}
if(edg[nod].empty())
chn[nod] = ++K;
else
chn[nod] = chn[ edg[nod][0] ];
nodes[ chn[nod] ].push_back(nod);
pos[nod] = int(nodes[ chn[nod] ].size()) - 1;
}
int main()
{
#ifdef FILE_IO
freopen("1.in", "r", stdin);
//freopen("1.out", "w", stdout);
#endif
scanf("%d", &N);
for(int i = 1; i <= N; i++) scanf("%d", &v[i]), nrm.add(v[i]);
nrm.normalize();
for(int i = 1; i <= N; i++) v[i] = nrm.get(v[i]);
for(int i = 1; i < N; i++)
{
int x, y;
scanf("%d%d", &x, &y);
edg[x].push_back(y);
edges.push_back({x, y});
}
DFS(1);
aib.init(N);
blocks[ chn[1] ].push_back({v[1], 1});
for(auto &e: edges)
{
int x = e.first, y = e.second;
int p = pos[x], c = chn[x];
blk.clear();
while(1)
{
int rem = int(nodes[c].size()) - p;
aux.clear();
while(rem)
{
if(blocks[c].back().second > rem)
{
aux.push_back({blocks[c].back().first, rem});
blocks[c][ int(blocks[c].size()) - 1 ].second -= rem;
break;
}
rem -= blocks[c].back().second;
aux.push_back(blocks[c].back());
blocks[c].pop_back();
}
reverse(aux.begin(), aux.end());
for(auto &x: aux) blk.push_back(x);
int cnt = int(nodes[c].size() - p);
if(chn[y] == c) cnt++;
blocks[c].push_back({v[y], cnt});
if(c == chn[1]) break;
int nod = f[ nodes[c].back() ];
c = chn[nod], p = pos[nod];
}
if(chn[x] != chn[y]) blocks[ chn[y] ].push_back({v[y], 1});
LL ans = 0LL;
for(auto &b: blk)
{
ans += 1LL * b.second * aib.Q(b.first - 1);
aib.U(b.first, b.second);
}
printf("%lld\n", ans);
for(auto &b: blk)
aib.U(b.first, -b.second);
}
return 0;
}
Compilation message (stderr)
construction.cpp: In member function 'void Normalizer::normalize()':
construction.cpp:34:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ord.size(); i++)
~~^~~~~~~~~~~~
construction.cpp: In member function 'void BinaryIndexedTree::U(int, int)':
construction.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; pos < aib.size(); pos += (pos & (-pos)))
~~~~^~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
construction.cpp:92:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= N; i++) scanf("%d", &v[i]), nrm.add(v[i]);
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
construction.cpp:98: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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |