QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #587961 | #9373. Query on Tree | tosania | WA | 71ms | 50664kb | C++14 | 12.8kb | 2024-09-24 23:01:24 | 2024-09-24 23:01:25 |
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 = 2e5 + 10;
ll MAX = 0x7fffffffffffff;
ll MAX_CAN = 4E14;
ll num_edge, head[N], q[N], hed, til, al[N], dfn[N], T, n, Q, shu[N], dfn_max[N], cnt, dui[N], lei;
int fat[N][11];
struct bfN
{
ll z;
int upper[11], lower_l[11];
int lower_r[11];
} bfn[N];
struct Edge
{
ll to, next;
} edge[N * 2];
struct node
{
ll z, l, r, laze_tag;
};
class seg_tree
{
public:
node z[2 * 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[2 * 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] = MAX;
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);
ll ik = 0;
T = read();
for (ll i = 0; i <= N; i++)
{
for (ll j = 0; j <= 10; j++)
{
bfn[i].lower_l[j] = MAX;
}
}
for (ll yyc = 1; yyc <= T; yyc++)
{
clear();
n = read();
Q = read();
for (ll i = 1; i <= n; i++)
{
shu[i] = read();
if (yyc == 1 && i == 1 && shu[i] == 71797802165245)
{
ik = 1;
}
}
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);
a.add(1, 0, 0, -MAX);
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: 0ms
memory: 48612kb
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: 64ms
memory: 48672kb
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: -100
Wrong Answer
time: 71ms
memory: 50664kb
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 -93292664256701 -93291942386514 74425923795990 -1057967076510 -93292321754544 74425228504438 74425430401539 -93293008979101 74425906008467 -1057533185261 -1057791207386 74424997886529 74424...
result:
wrong answer 10th lines differ - expected: '-93292817648557', found: '-93292664256701'