QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #588025 | #9373. Query on Tree | tosania | WA | 4ms | 77356kb | C++14 | 12.7kb | 2024-09-24 23:44:24 | 2024-09-24 23:44:24 |
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=99670597808196){
cout<<"s";
}
if (maxx <= -MAX_CAN)
{
cout << "GG\n";
}
else
cout << maxx << endl;
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 77356kb
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 s99670597808196 5 s99670597808196
result:
wrong answer 3rd lines differ - expected: '1', found: 's99670597808196'