#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
using namespace std;
const int N = 4000 + 7;
const int inf = 1e9 + 7;
int a[N], pr[N];
struct con
{
int l, r;
ll sm;
con()
{
l = r = sm = 0;
}
}t[N * 7];
int cnt;
void update(int v, int tl, int tr, int pos, int x)
{
if (tl == tr)
{
t[v].sm = max(t[v].sm + x, 0LL);
}
else
{
int mid = (tl + tr) >> 1;
if (mid >= pos)
{
if (!t[v].l)
t[v].l = ++cnt;
update(t[v].l, tl, mid, pos, x);
}
else
{
if (!t[v].r)
t[v].r = ++cnt;
update(t[v].r, mid + 1, tr, pos, x);
}
if (!t[v].l)t[v].l = ++cnt;
if (!t[v].r)t[v].r = ++cnt;
t[v].sm = t[t[v].l].sm + t[t[v].r].sm;
}
}
ll get(int v, int tl, int tr, int l, int r)
{
if (tl > r || l > tr)return 0LL;
if (l <= tl && tr <= r)
{
return t[v].sm;
}
else
{
int mid = (tl + tr) >> 1;
if (!t[v].l)
t[v].l = ++cnt;
if (!t[v].r)
t[v].r = ++cnt;
return get(t[v].l, tl, mid, l, r) + get(t[v].r, mid + 1, tr, l, r);
}
}
deque<int>dq;
void dfs(int v)
{
if (v == 0)
return;
dq.pf(a[v]);
dfs(pr[v]);
}
void conquer(int v)
{
ll ans = 0;
dfs(v);
cnt = 1;
for (int i = 0; i < dq.size(); i++)
{
ans += get(1, 1, inf, dq[i] + 1, inf);
update(1, 1, inf, dq[i], 1);
}
// for (int i = 0; i < dq.size(); i++)
// update(1, 1, inf, dq[i], -inf);
memset(t, 0, sizeof(t));
dq.clear();
printf("%lld\n", ans);
}
void upd(int v, int x)
{
if (v == 0)return;
a[v] = x;
upd(pr[v], x);
}
main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i < n; i++)
{
int q, w;
scanf("%d%d", &q, &w);
if (i == 1)
{
puts("0");
pr[w] = q;
a[q] = a[w];
continue;
}
conquer(q);
upd(q, a[w]);
pr[w] = q;
}
}
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
using namespace std;
const int N = 4000 + 7;
const int inf = 1e9 + 7;
int a[N], pr[N];
struct con
{
int l, r;
ll sm;
con()
{
l = r = sm = 0;
}
}t[N * 7];
int cnt;
void update(int v, int tl, int tr, int pos, int x)
{
if (tl == tr)
{
t[v].sm = max(t[v].sm + x, 0LL);
}
else
{
int mid = (tl + tr) >> 1;
if (mid >= pos)
{
if (!t[v].l)
t[v].l = ++cnt;
update(t[v].l, tl, mid, pos, x);
}
else
{
if (!t[v].r)
t[v].r = ++cnt;
update(t[v].r, mid + 1, tr, pos, x);
}
if (!t[v].l)t[v].l = ++cnt;
if (!t[v].r)t[v].r = ++cnt;
t[v].sm = t[t[v].l].sm + t[t[v].r].sm;
}
}
ll get(int v, int tl, int tr, int l, int r)
{
if (tl > r || l > tr)return 0LL;
if (l <= tl && tr <= r)
{
return t[v].sm;
}
else
{
int mid = (tl + tr) >> 1;
if (!t[v].l)
t[v].l = ++cnt;
if (!t[v].r)
t[v].r = ++cnt;
return get(t[v].l, tl, mid, l, r) + get(t[v].r, mid + 1, tr, l, r);
}
}
deque<int>dq;
void dfs(int v)
{
if (v == 0)
return;
dq.pf(a[v]);
dfs(pr[v]);
}
void conquer(int v)
{
ll ans = 0;
dfs(v);
cnt = 1;
for (int i = 0; i < dq.size(); i++)
{
ans += get(1, 1, inf, dq[i] + 1, inf);
update(1, 1, inf, dq[i], 1);
}
// for (int i = 0; i < dq.size(); i++)
// update(1, 1, inf, dq[i], -inf);
memset(t, 0, sizeof(t));
dq.clear();
printf("%lld\n", ans);
}
void upd(int v, int x)
{
if (v == 0)return;
a[v] = x;
upd(pr[v], x);
}
main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i < n; i++)
{
int q, w;
scanf("%d%d", &q, &w);
if (i == 1)
{
puts("0");
pr[w] = q;
a[q] = a[w];
continue;
}
conquer(q);
upd(q, a[w]);
pr[w] = q;
}
}
Compilation message
construction.cpp: In function 'void conquer(int)':
construction.cpp:93:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < dq.size(); i++)
~~^~~~~~~~~~~
construction.cpp: At global scope:
construction.cpp:112:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
construction.cpp:149:11: error: redefinition of 'const int N'
const int N = 4000 + 7;
^
construction.cpp:11:11: note: 'const int N' previously defined here
const int N = 4000 + 7;
^
construction.cpp:150:11: error: redefinition of 'const int inf'
const int inf = 1e9 + 7;
^~~
construction.cpp:12:11: note: 'const int inf' previously defined here
const int inf = 1e9 + 7;
^~~
construction.cpp:152:8: error: redefinition of 'int a [4007]'
int a[N], pr[N];
^
construction.cpp:14:5: note: 'int a [4007]' previously declared here
int a[N], pr[N];
^
construction.cpp:152:15: error: redefinition of 'int pr [4007]'
int a[N], pr[N];
^
construction.cpp:14:11: note: 'int pr [4007]' previously declared here
int a[N], pr[N];
^~
construction.cpp:154:8: error: redefinition of 'struct con'
struct con
^~~
construction.cpp:16:8: note: previous definition of 'struct con'
struct con
^~~
construction.cpp:163:9: error: conflicting declaration 'int t [28049]'
}t[N * 7];
^
construction.cpp:25:2: note: previous declaration as 'con t [28049]'
}t[N * 7];
^
construction.cpp:164:5: error: redefinition of 'int cnt'
int cnt;
^~~
construction.cpp:26:5: note: 'int cnt' previously declared here
int cnt;
^~~
construction.cpp: In function 'void update(int, int, int, int, int)':
construction.cpp:166:6: error: redefinition of 'void update(int, int, int, int, int)'
void update(int v, int tl, int tr, int pos, int x)
^~~~~~
construction.cpp:28:6: note: 'void update(int, int, int, int, int)' previously defined here
void update(int v, int tl, int tr, int pos, int x)
^~~~~~
construction.cpp: In function 'long long int get(int, int, int, int, int)':
construction.cpp:196:4: error: redefinition of 'long long int get(int, int, int, int, int)'
ll get(int v, int tl, int tr, int l, int r)
^~~
construction.cpp:58:4: note: 'long long int get(int, int, int, int, int)' previously defined here
ll get(int v, int tl, int tr, int l, int r)
^~~
construction.cpp: At global scope:
construction.cpp:216:11: error: redefinition of 'std::deque<int> dq'
deque<int>dq;
^~
construction.cpp:78:11: note: 'std::deque<int> dq' previously declared here
deque<int>dq;
^~
construction.cpp: In function 'void dfs(int)':
construction.cpp:218:6: error: redefinition of 'void dfs(int)'
void dfs(int v)
^~~
construction.cpp:80:6: note: 'void dfs(int)' previously defined here
void dfs(int v)
^~~
construction.cpp: In function 'void conquer(int)':
construction.cpp:225:6: error: redefinition of 'void conquer(int)'
void conquer(int v)
^~~~~~~
construction.cpp:87:6: note: 'void conquer(int)' previously defined here
void conquer(int v)
^~~~~~~
construction.cpp:231:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < dq.size(); i++)
~~^~~~~~~~~~~
construction.cpp: In function 'void upd(int, int)':
construction.cpp:242:6: error: redefinition of 'void upd(int, int)'
void upd(int v, int x)
^~~
construction.cpp:104:6: note: 'void upd(int, int)' previously defined here
void upd(int v, int x)
^~~
construction.cpp: At global scope:
construction.cpp:250:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
construction.cpp: In function 'int main()':
construction.cpp:250:1: error: redefinition of 'int main()'
main()
^~~~
construction.cpp:112:1: note: 'int main()' previously defined here
main()
^~~~
construction.cpp: In function 'int main()':
construction.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
construction.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
construction.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &q, &w);
~~~~~^~~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:254:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
construction.cpp:257:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
construction.cpp:262:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &q, &w);
~~~~~^~~~~~~~~~~~~~~~
