#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define M -100000000000ll
using namespace std;
const int N = 100020;
map < int, int > mp;
int n, m, timer;
int a[N], in[N], tn[N], out[N], P[N][20], dep[N];
pair < int, int > g[N];
vector < pair < int, int > > c;
vector < int > G[N];
int T[4 * N], tot;
ll t[4 * N];
void go(int v)
{
for(int k = 1; k < 20; ++ k)
P[v][k] = P[P[v][k - 1]][k - 1];
dep[v] = dep[P[v][0]] + 1;
in[v] = ++ timer;
tn[timer] = v;
for(auto x : G[v])
P[x][0] = v, go(x);
out[v] = timer + 1;
}
int lca(int v, int u)
{
if(dep[u] < dep[v])
swap(u, v);
for(int k = 19; k >= 0; -- k)
if(dep[P[u][k]] >= dep[v])
u = P[u][k];
if(u == v)
return v;
for(int k = 19; k >= 0; -- k)
if(P[u][k] != P[v][k])
u = P[u][k], v = P[v][k];
return P[u][0];
}
void update(int v, int tl, int tr, int l, int x)
{
if(tl > l || tr <= l)
return;
if(tl == tr - 1)
{
T[v] = x;
return;
}
update(v + v, tl, tl + tr >> 1, l, x);
update(v + v + 1, tl + tr >> 1, tr, l, x);
T[v] = max(T[v + v], T[v + v + 1]);
}
int get(int v, int tl, int tr, int l, int r)
{
if(tr <= l || r <= tl)
return 0;
if(l <= tl && tr <= r)
return T[v];
int x, y;
x = get(v + v, tl, tl + tr >> 1, l, r);
y = get(v + v + 1, tl + tr >> 1, tr, l, r);
return max(x, y);
}
int right(int v, int tl, int tr, int ind, int x)
{
tot ++;
if(tr <= ind)
return 0;
if(tl < ind)
{
int y = right(v + v, tl, tl + tr >> 1, ind, x);
if(y)
return y;
return right(v + v + 1, tl + tr >> 1, tr, ind, x);
}
if(T[v] <= x)
return 0;
if(tl == tr - 1)
return tn[tl];
if(T[v + v] <= x)
return right(v + v + 1, tl + tr >> 1, tr, ind, x);
return right(v + v, tl, tl + tr >> 1, ind, x);
}
int left(int v, int tl, int tr, int ind, int x)
{
tot ++;
if(tl >= ind)
return 0;
if(ind < tr)
{
int y = left(v + v + 1, tl + tr >> 1, tr, ind, x);
if(y)
return y;
return left(v + v, tl, tl + tr >> 1, ind, x);
}
if(T[v] <= x)
return 0;
if(tl == tr - 1)
return tn[tl];
if(T[v + v + 1] <= x)
return left(v + v, tl, tl + tr >> 1, ind, x);
return left(v + v + 1, tl + tr >> 1, tr, ind, x);
}
void deep(int v)
{
if(v == 0)
return;
int x = get(1, 1, n + 1, in[v], out[v]);
int r = right(1, 1, n + 1, out[v], x); r = lca(r, v);
int l = left(1, 1, n + 1, in[v], x); l = lca(l, v);
l = dep[l] < dep[r] ? r : l;
c.push_back({a[g[x].sc], dep[v] - dep[l]});
deep(l);
}
void upd(int v, int tl, int tr, int l, ll x)
{
if(tl > l || tr <= l)
return;
if(tl == tr - 1)
{
if(x < 0)
t[v] = 0;
else
t[v] += x;
return;
}
upd(v + v, tl, tl + tr >> 1, l, x);
upd(v + v + 1, tl + tr >> 1, tr, l, x);
t[v] = t[v + v] + t[v + v + 1];
}
ll gt(int v, int tl, int tr, int l)
{
if(tl >= l)
return 0;
if(tr <= l)
return t[v];
return gt(v + v, tl, tl + tr >> 1, l) + gt(v + v + 1, tl + tr >> 1, tr, l);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i)
scanf("%d", &a[i]), mp[a[i]] = 1;
m = 1;
for(map < int, int >::iterator it = mp.begin(); it != mp.end(); it ++)
it -> sc = m ++;
for(int i = 1; i <= n; ++ i)
a[i] = mp[a[i]];
for(int i = 2; i <= n; ++ i)
{
scanf("%d %d", &g[i].fr, &g[i].sc);
G[g[i].fr].push_back(g[i].sc);
}
go(1);
update(1, 1, n + 1, in[1], 1);
g[1].sc = 1;
int S = 0;
for(int i = 2; i <= n; ++ i)
{
c.clear();
deep(g[i].fr);
ll answer = 0;
S += c.size();
for(int j = 0; j < c.size(); ++ j)
{
answer += c[j].sc * gt(1, 1, m, c[j].fr);
upd(1, 1, m, c[j].fr, c[j].sc);
}
for(int j = 0; j < c.size(); ++ j)
upd(1, 1, m, c[j].fr, -10);
if(tot > S * 30)
return 0;
printf("%lld\n", answer);
update(1, 1, n + 1, in[g[i].sc], i);
}
}
Compilation message
construction.cpp: In function 'void update(int, int, int, int, int)':
construction.cpp:56:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
update(v + v, tl, tl + tr >> 1, l, x);
~~~^~~~
construction.cpp:57:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
update(v + v + 1, tl + tr >> 1, tr, l, x);
~~~^~~~
construction.cpp: In function 'int get(int, int, int, int, int)':
construction.cpp:68:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
x = get(v + v, tl, tl + tr >> 1, l, r);
~~~^~~~
construction.cpp:69:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
y = get(v + v + 1, tl + tr >> 1, tr, l, r);
~~~^~~~
construction.cpp: In function 'int right(int, int, int, int, int)':
construction.cpp:80:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int y = right(v + v, tl, tl + tr >> 1, ind, x);
~~~^~~~
construction.cpp:83:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return right(v + v + 1, tl + tr >> 1, tr, ind, x);
~~~^~~~
construction.cpp:90:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return right(v + v + 1, tl + tr >> 1, tr, ind, x);
~~~^~~~
construction.cpp:91:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return right(v + v, tl, tl + tr >> 1, ind, x);
~~~^~~~
construction.cpp: In function 'int left(int, int, int, int, int)':
construction.cpp:101:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int y = left(v + v + 1, tl + tr >> 1, tr, ind, x);
~~~^~~~
construction.cpp:104:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return left(v + v, tl, tl + tr >> 1, ind, x);
~~~^~~~
construction.cpp:111:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return left(v + v, tl, tl + tr >> 1, ind, x);
~~~^~~~
construction.cpp:112:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return left(v + v + 1, tl + tr >> 1, tr, ind, x);
~~~^~~~
construction.cpp: In function 'void upd(int, int, int, int, long long int)':
construction.cpp:139:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
upd(v + v, tl, tl + tr >> 1, l, x);
~~~^~~~
construction.cpp:140:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
upd(v + v + 1, tl + tr >> 1, tr, l, x);
~~~^~~~
construction.cpp: In function 'long long int gt(int, int, int, int)':
construction.cpp:150:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return gt(v + v, tl, tl + tr >> 1, l) + gt(v + v + 1, tl + tr >> 1, tr, l);
~~~^~~~
construction.cpp:150:60: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return gt(v + v, tl, tl + tr >> 1, l) + gt(v + v + 1, tl + tr >> 1, tr, l);
~~~^~~~
construction.cpp: In function 'int main()':
construction.cpp:179:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < c.size(); ++ j)
~~^~~~~~~~~~
construction.cpp:184:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < c.size(); ++ j)
~~^~~~~~~~~~
construction.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
construction.cpp:158:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]), mp[a[i]] = 1;
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
construction.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &g[i].fr, &g[i].sc);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2792 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2840 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2916 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
2992 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2792 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2840 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2916 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
2992 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2792 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2840 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2916 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
2992 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
