QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#588053 | #9373. Query on Tree | tosania | WA | 1601ms | 102676kb | C++14 | 12.6kb | 2024-09-24 23:58:08 | 2024-09-24 23:58:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
ll al = 0, fh = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
fh = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0')
{
al = al * 10 + ch - '0';
ch = getchar();
}
return al * fh;
}
const ll N = 4e5 + 10;
ll MAX = 0x7fffffffffffff;
ll MAX_CAN = 4e15;
ll num_edge, hed, til, T, n, Q, shu[N], cnt, lei;
int fat[N][11], head[N], q[N], al[N], dfn[N], dfn_max[N];
struct bfN
{
ll z;
int upper[11], lower_l[11];
int lower_r[11];
} bfn[N];
struct Edge
{
int to, next;
} edge[N * 2];
struct node
{
int l, r ;
ll z,laze_tag;
};
class seg_tree
{
public:
node z[8 * N];
void build(ll now, ll l, ll r)
{
this->z[now].l = l;
this->z[now].r = r;
this->z[now].laze_tag = 0;
this->z[now].z = 0;
if (l != r)
{
ll mid = (l + r) / 2;
this->build(now * 2, l, mid);
this->build(now * 2 + 1, mid + 1, r);
}
}
void add(ll now, ll l, ll r, ll v)
{
ll lel = this->z[now].l, rr = this->z[now].r;
if (lel > r || rr < l || l > r || r <= 0)
return;
if (lel == rr)
{
this->z[now].z += v;
return;
}
else if (lel >= l && rr <= r)
{
this->z[now].laze_tag += v;
return;
}
else
{
add(now * 2, l, r, v);
add(now * 2 + 1, l, r, v);
this->z[now].z = max(this->z[now * 2].z + this->z[now * 2].laze_tag, this->z[now * 2 + 1].z + this->z[now * 2 + 1].laze_tag);
}
}
ll query(ll now, ll l, ll r)
{
ll lel = this->z[now].l, rr = this->z[now].r;
if (lel > r || rr < l || l > r || r <= 0)
return -MAX;
if (lel == rr)
{
return this->z[now].z;
}
else if (lel >= l && rr <= r)
{
return this->z[now].z + this->z[now].laze_tag;
}
else
{
return max(query(now * 2, l, r), query(now * 2 + 1, l, r)) + this->z[now].laze_tag;
}
}
} a, t;
class seg_tree_jia
{
public:
node z[8 * N];
void build(ll now, ll l, ll r)
{
this->z[now].l = l;
this->z[now].r = r;
this->z[now].laze_tag = 0;
this->z[now].z = 0;
if (l != r)
{
ll mid = (l + r) / 2;
this->build(now * 2, l, mid);
this->build(now * 2 + 1, mid + 1, r);
}
}
void add(ll now, ll l, ll r, ll v)
{
ll lel = this->z[now].l, rr = this->z[now].r;
if (lel > r || rr < l)
return;
if (lel == rr)
{
this->z[now].z += v;
return;
}
else if (lel >= l && rr <= r)
{
this->z[now].laze_tag += v;
return;
}
else
{
add(now * 2, l, r, v);
add(now * 2 + 1, l, r, v);
}
}
ll query(ll now, ll l, ll r)
{
// return 0;
if (l > r)
return 0;
if (r <= 0)
return 0;
ll lel = this->z[now].l, rr = this->z[now].r;
if (lel > r || rr < l)
return 0;
if (lel == rr)
{
return this->z[now].z;
}
else
{
return query(now * 2, l, r) + query(now * 2 + 1, l, r) + this->z[now].laze_tag;
}
}
} b;
void add_edge(ll from, ll to)
{
edge[++num_edge].to = to;
edge[num_edge].next = head[from];
head[from] = num_edge;
}
void bfs(ll now)
{
hed = til = 0;
q[++til] = now;
al[now] = 1;
bfn[now].z = ++cnt;
bfn[now].lower_l[0] = bfn[now].z;
bfn[now].lower_r[0] = bfn[now].z;
bfn[now].upper[0] = now;
while (hed < til)
{
hed++;
for (ll i = head[q[hed]]; i; i = edge[i].next)
{
if (al[edge[i].to] == 0)
{
al[edge[i].to] = 1;
bfn[edge[i].to].z = ++cnt;
q[++til] = edge[i].to;
bfn[edge[i].to].lower_l[0] = cnt;
bfn[edge[i].to].lower_r[0] = cnt;
bfn[edge[i].to].upper[0] = edge[i].to;
for (ll j = 1; j <= 10; j++)
{
bfn[edge[i].to].upper[j] = bfn[q[hed]].upper[j - 1];
}
}
}
}
}
void dfs(ll now, ll fa = 0)
{
dfn[now] = ++cnt;
fat[now][0] = now;
for (ll i = 1; i <= 10; i++)
{
fat[now][i] = fat[fa][i - 1];
}
ll ok = 0;
for (ll i = head[now]; i; i = edge[i].next)
{
if (edge[i].to != fa)
{
dfs(edge[i].to, now);
for (ll j = 1; j <= 10; j++)
{
if (ok == 0)
bfn[now].lower_l[j] = bfn[edge[i].to].lower_l[j - 1], bfn[now].lower_r[j] = bfn[edge[i].to].lower_r[j - 1];
else
{
bfn[now].lower_l[j] = min(bfn[now].lower_l[j], bfn[edge[i].to].lower_l[j - 1]);
bfn[now].lower_r[j] = max(bfn[now].lower_r[j], bfn[edge[i].to].lower_r[j - 1]);
}
}
ok = 1;
}
}
dfn_max[now] = cnt;
}
void clear()
{
num_edge = 0;
for (ll i = 0; i <= n; i++)
{
head[i] = al[i] = dfn[i] = shu[i] = dfn_max[i] = bfn[i].z = 0;
for (ll j = 0; j <= 10; j++)
{
bfn[i].lower_l[j] = 1e9+7;
bfn[i].lower_r[j] = bfn[i].upper[j] = 0;
}
for (ll j = 0; j <= 10; j++)
fat[i][j] = 0;
}
}
signed main()
{
// freopen("D.in","r",stdin);
T = read();
for (ll i = 0; i <= N; i++)
{
for (ll j = 0; j <= 10; j++)
{
bfn[i].lower_l[j] = 1e10+7;
}
}
for (ll yyc = 1; yyc <= T; yyc++)
{
clear();
n = read();
Q = read();
for (ll i = 1; i <= n; i++)
{
shu[i] = read();
}
for (ll i = 1; i < n; i++)
{
ll u = read(), v = read();
add_edge(u, v);
add_edge(v, u);
}
a.build(1, 1, n);
b.build(1, 1, n);
t.build(1, 1, n);
cnt = 0;
bfs(1);
cnt = 0;
dfs(1);
for (ll i = 1; i <= n; i++)
{
a.add(1, bfn[i].z, bfn[i].z, shu[i]);
}
for (ll i = 1; i <= n; i++)
{
t.add(1, dfn[i], dfn[i], a.query(1, bfn[i].lower_l[10], bfn[i].lower_r[10]));
}
for (ll p = 1; p <= Q; p++)
{
ll o = read();
lei++;
if (o == 1)
{
ll x = read(), k = read(), v = read();
ll l = bfn[x].lower_l[k], r = bfn[x].lower_r[k];
a.add(1, l, r, v);
ll zu = fat[x][10 - k];
//t.add(1, dfn[fat[x][10 - k]], dfn[fat[x][10 - k]], b.query(1, dfn[fat[x][10 - k]], dfn[fat[x][10 - k]]) + a.query(1, bfn[zu].lower_l[10], bfn[zu].lower_r[10]) - t.query(1, dfn[fat[x][10 - k]], dfn[fat[x][10 - k]]));
ll maxx = a.query(1, l, r) + b.query(1, dfn[fat[x][10 - k]], dfn[fat[x][10 - k]]);
for (ll i = 1; i <= k; i++)
{
ll zu = bfn[x].upper[i];
ll jia = b.query(1, dfn[fat[zu][10 + i - k]], dfn[fat[zu][10 + i - k]]);
if (zu != 0)
{
l = bfn[zu].lower_l[k - i], r = bfn[zu].lower_r[k - i];
zu = bfn[x].upper[i - 1];
if (i != k)
{
ll lel = bfn[zu].lower_l[k - i - 1], rr = bfn[zu].lower_r[k - i - 1];
if (lel <= rr && lel >= l && rr <= r)
{
if (l <= lel - 1)
{
a.add(1, l, lel - 1, v);
maxx = max(maxx, a.query(1, l, lel - 1) + jia);
}
if (rr + 1 <= r)
{
a.add(1, rr + 1, r, v);
maxx = max(maxx, a.query(1, rr + 1, r) + jia);
}
}
else
{
a.add(1, l, r, v);
maxx = max(maxx, a.query(1, l, r) + jia);
}
}
else
{
a.add(1, l, r, v);
maxx = max(maxx, a.query(1, l, r) + jia);
}
ll zuu = fat[zu][10 - (k - i)];
// t.add(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]], b.query(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]]) + a.query(1, bfn[zuu].lower_l[10], bfn[zuu].lower_r[10]) - t.query(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]]));
}
}
if (maxx <= -MAX_CAN)
{
cout << "GG\n";
}
else
cout << maxx << endl;
}
else if (o == 2)
{
ll x = read(), k = read(), v = read(), maxx = -MAX;
for (ll i = 0; i <= k; i++)
{
ll zu = fat[x][i], all = 0;
if (zu == 0)
all = 1, zu = 1;
if (zu == 1 && i != k)
{
all = 1;
}
ll jia = b.query(1, dfn[fat[zu][10 + i - k]], dfn[fat[zu][10 + i - k]]);
ll l = bfn[zu].lower_l[k - i], r = bfn[zu].lower_r[k - i];
a.add(1, l, r, v);
ll zuu = fat[zu][10 - (k - i)];
//t.add(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]], b.query(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]]) + a.query(1, bfn[zuu].lower_l[10], bfn[zuu].lower_r[10]) - t.query(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]]));
maxx = max(maxx, a.query(1, l, r) + jia);
if (i != k && all == 0)
{
k -= 1;
jia = b.query(1, dfn[fat[zu][10 + i - k]], dfn[fat[zu][10 + i - k]]);
l = bfn[zu].lower_l[k - i], r = bfn[zu].lower_r[k - i];
a.add(1, l, r, v);
ll zuu = fat[zu][10 - (k - i)];
t.add(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]], b.query(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]]) + a.query(1, bfn[zuu].lower_l[10], bfn[zuu].lower_r[10]) - t.query(1, dfn[fat[zu][10 - (k - i)]], dfn[fat[zu][10 - (k - i)]]));
maxx = max(maxx, a.query(1, l, r) + jia);
k += 1;
}
}
if (maxx <= -MAX_CAN)
{
cout << "GG\n";
}
else
cout << maxx << endl;
}
else
{
ll x = read(), v = read(), maxx = -MAX;
for (ll i = 0; i < 10; i++)
{
a.add(1, bfn[x].lower_l[i], bfn[x].lower_r[i], v);
ll zu = fat[x][10 - i];
t.add(1, dfn[zu], dfn[zu], b.query(1, dfn[zu], dfn[zu]) + a.query(1, bfn[zu].lower_l[10], bfn[zu].lower_r[10]) - t.query(1, dfn[zu], dfn[zu]));
maxx = max(maxx, a.query(1, bfn[x].lower_l[i], bfn[x].lower_r[i]) + b.query(1, dfn[zu], dfn[zu]));
}
b.add(1, dfn[x], dfn_max[x], v);
t.add(1, dfn[x], dfn_max[x], v);
// cout<<dfn[x]<<" "<<dfn_max[x]<<" "<<v<<":";
maxx = max(maxx, t.query(1, dfn[x], dfn_max[x]));
if (maxx <= -MAX_CAN)
{
cout << "GG\n";
}
else
cout << maxx << endl;
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 77312kb
input:
1 5 5 1 2 1 3 2 1 2 2 3 2 4 4 5 2 2 1 0 1 2 1 3 3 4 -5 2 5 2 3 3 2 -1
output:
3 6 1 5 4
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 40ms
memory: 79408kb
input:
10000 3 9 42973045452542 34994498886390 -91733395797555 1 3 1 2 1 1 5 -71952967 3 1 -816873082 1 1 5 -842437577 2 3 7 254550528 3 3 -854082700 2 3 2 699808309 3 3 554885567 1 2 7 595565507 1 3 0 -318374053 3 2 -63158159333100 77264362049163 -99188430131116 1 2 3 2 2 2 4 -305866230 3 1 -549738403 3 5...
output:
GG 42972228579460 GG 42972483129988 -91734812202809 42973182938297 -91733557508933 GG -91733875882986 77264056182933 77263506444530 7065382376488 7065749360235 7066534912965 -85115611272570 -85114714781312 96492412785032 -20428913156111 -20428197540063 96491742171666 -14945310996805 96491180203461 -...
result:
ok 200000 lines
Test #3:
score: 0
Accepted
time: 88ms
memory: 79452kb
input:
10000 4 32 -1057044448491 -93293078803919 -24212938548357 74427756948193 1 3 1 2 3 4 3 1 -82365883 1 2 9 -730670945 2 4 2 -618745828 2 1 2 774032949 3 3 6733210 3 3 -843683844 3 1 327410390 3 1 -865685600 1 4 6 -951367966 3 2 107763506 1 3 2 721870187 2 3 3 -530847597 2 2 1 451029291 3 2 231297873 3...
output:
74427674582310 GG 74427055836482 74427829869431 74427836602641 74426992918797 74427320329187 74426454643587 GG -93292817648557 -93292095778370 74425923795990 -1057589620769 -93291944298803 74425228504438 74425430401539 -93291936231808 74425906008467 GG -1058067327518 74424997886529 74424370598990 74...
result:
ok 200000 lines
Test #4:
score: 0
Accepted
time: 71ms
memory: 77352kb
input:
10000 5 21 -17119694111919 -49543801764535 15340078463236 -13731655847398 -41385234314814 3 2 1 5 1 4 1 2 3 5 865538081 3 4 551893736 2 3 9 797578233 1 3 0 -657534941 3 4 -507570975 1 1 2 352656478 3 5 951666995 2 5 3 524459610 3 4 819153725 2 4 0 955588629 3 5 -451248313 1 3 0 -251438755 1 4 0 -707...
output:
-41384368776733 -13731103953662 15340876041469 15340218506528 -13730813946404 15340571163006 -41382619531505 15341095622616 -13729470333069 -13728514744440 -41382546320208 15340844183861 -13729221899958 15340255675017 -13729490336654 -13729529150761 -13729624738248 15341124008689 15341173814500 GG -...
result:
ok 200000 lines
Test #5:
score: 0
Accepted
time: 108ms
memory: 77316kb
input:
10000 7 53 -49257878340663 65913602617244 -77586447275975 37912663831730 -29965751459870 -24028915786606 -20711244730875 2 1 3 1 4 6 1 5 7 1 2 4 1 6 4 -614276625 3 7 -430532617 3 3 -970301980 1 1 4 767992650 2 1 4 88036223 2 3 5 -930151770 3 3 -816226996 1 2 1 -696978838 2 1 1 -877781309 2 5 2 58619...
output:
-20711859007500 -20712289540117 -77588031854580 GG 65913690653467 65912760501697 -77589690197123 37911124737345 65911882720388 65912468916628 65911745912774 -29967336843362 65911988615088 GG 37910494006281 65912545393218 -49259038263999 GG 65913255260627 GG GG 65912963550828 -24029074909413 65912862...
result:
ok 200000 lines
Test #6:
score: 0
Accepted
time: 100ms
memory: 77368kb
input:
10000 10 4 71797802165245 -54234031880796 29183815458453 29504172959957 49372193603523 -16185389362615 39453295094243 663036651923 96744787191200 -50620611104201 5 8 5 1 1 2 4 7 7 10 2 4 5 6 3 9 3 2 3 7 -830615007 1 2 6 637860195 2 7 7 -843886558 3 8 273999944 10 8 -33479821641433 91082116968197 -34...
output:
39452464479236 GG 96743943304642 662466765309 91246631814706 -29877405744477 GG GG 91081604757708 GG 91246614330784 -29877381879548 -4361386733251 89595437158302 -4360828297147 19337184792075 89595109336295 89594748412265 19336971357477 89594978989869 86993545918633 -84286253125550 GG GG 52174855696...
result:
ok 200000 lines
Test #7:
score: 0
Accepted
time: 88ms
memory: 77312kb
input:
10000 3 9 42973045452542 34994498886390 -91733395797555 2 3 2 1 3 1 -988613092 1 2 0 308890489 1 1 0 472776476 2 2 2 -122992202 2 3 1 831940219 3 3 -612896282 3 3 -536438981 1 1 0 161104440 2 1 1 354965461 3 2 77441670935132 -63158159333100 77264362049163 3 1 2 1 1 3 4 -20585631 1 1 6 747193249 3 5 ...
output:
42972056839450 34993819163787 42972529615926 42972406623724 34994528111804 -91734288358912 -91734824797893 42972567728164 42972922693625 GG GG GG 7064655135811 -61568732738930 7065157020537 -61568593058530 80122234728388 80122047274326 80122140239806 80121956639200 80121963373184 80121401404979 9259...
result:
ok 200000 lines
Test #8:
score: 0
Accepted
time: 76ms
memory: 77348kb
input:
10000 4 32 -1057044448491 -93293078803919 -24212938548357 74427756948193 3 2 4 1 1 2 1 2 8 639477246 1 4 0 510694922 2 1 0 421373363 2 3 4 -843809269 3 1 -620938865 3 3 -933234989 1 3 3 458028025 1 4 6 -951367966 3 2 107763506 1 3 2 721870187 2 3 3 -530847597 2 2 1 451029291 3 2 231297873 3 1 -69529...
output:
GG 74428267643115 -1056623075128 74427423833846 74426802894981 -24215336531480 74427260923006 GG -24215228767974 -1057365953075 74426730075409 -1057445771381 -24215077288407 74426034783857 74426236680958 -24215069221412 74426712287886 74427585548383 74427327526258 -24215759758547 -24216387046086 744...
result:
ok 200000 lines
Test #9:
score: 0
Accepted
time: 75ms
memory: 77352kb
input:
10000 5 21 -17119694111919 -49543801764535 15340078463236 -13731655847398 -41385234314814 1 2 4 1 5 1 1 3 3 4 -183603675 1 1 6 750831651 2 4 2 -112044052 2 5 0 487266103 2 4 7 623494631 2 3 6 -758745863 2 5 3 524459610 3 4 819153725 2 4 0 955588629 3 5 -451248313 1 3 0 -251438755 1 4 0 -707155518 3 ...
output:
-13731839451073 GG 15339966419184 -41384859092763 15340589913815 15339831167952 15340355627562 -13730743133022 -13729787544393 -41384921132698 15340104188807 -13730494699911 -49544113109053 -13730763136607 15340065374700 -13730897538201 -17118548613921 15340115180511 GG -41384542096059 1534095454059...
result:
ok 200000 lines
Test #10:
score: 0
Accepted
time: 120ms
memory: 77292kb
input:
10000 7 53 -49257878340663 65913602617244 -77586447275975 37912663831730 -29965751459870 -24028915786606 -20711244730875 6 5 6 7 3 6 5 4 5 2 1 7 1 2 1 -902483856 2 2 0 -166019888 1 2 6 773740058 1 7 4 332162805 3 4 483966804 2 1 8 -161176455 2 6 2 999609920 2 2 1 575504367 1 2 2 -125436309 1 7 6 -85...
output:
-29966653943726 65913436597356 GG GG 37913147798534 65913275420901 65914275030821 65914850535188 37913860795690 GG 65915321019354 65915455681128 65915560380329 65915183127659 65914812218108 65915548812492 65916224155305 65915243014798 -20710396693949 GG 65915329685860 65915917517754 65915625807955 6...
result:
ok 200000 lines
Test #11:
score: 0
Accepted
time: 104ms
memory: 77312kb
input:
10000 10 4 71797802165245 -54234031880796 29183815458453 29504172959957 49372193603523 -16185389362615 39453295094243 663036651923 96744787191200 -50620611104201 3 4 3 8 5 10 8 1 6 2 7 6 10 3 8 9 5 7 3 10 272721546 2 10 4 618153907 3 8 763987349 1 9 7 870230974 10 8 -13468051963531 -33479821641433 9...
output:
49372466325069 96745405345107 96746169332456 -54231506787020 91247244061845 91246513437933 -33254303623674 -34062728633884 38205426400070 91082413811192 -13468602472782 GG 86995519872619 10278075155744 86995188030179 86995444966527 19338147521978 86995117144520 86994756220490 19337573163350 -9437093...
result:
ok 200000 lines
Test #12:
score: -100
Wrong Answer
time: 1601ms
memory: 102676kb
input:
5 100000 10278 -33062210930377 -27859969846302 -17580975150961 82421468622525 73124685670220 24605270582441 -85306160207816 -94488582195355 85451638721967 61110610044303 20119327748559 28059853591446 40777043818126 -26083158668773 -86932609818311 -80046664707280 36276301345898 72062141434820 -521113...
output:
99730096363045 -53142619895885 62633703474374 91065884890424 95913832039203 71963014593268 -73718672703414 88512243346245 95865153100847 20076236503631 -34284711719410 39055157031710 89757297384484 10950553757520 74269720205379 -9148723701106 -8854522652340 30148659190315 43163551215290 403669992467...
result:
wrong answer 71719th lines differ - expected: '99347729258664', found: '99346937492742'