QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#587427 | #9373. Query on Tree | tosania | WA | 82ms | 77384kb | C++14 | 11.7kb | 2024-09-24 19:53:51 | 2024-09-24 19:53:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int 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 int N = 2e5 + 10;
int MAX = 0x7fffffffffffff;
int MAX_CAN = 4E14;
int num_edge, head[N], q[N], hed, til, al[N], dfn[N], T, n, Q, shu[N], fat[N][11], dfn_max[N], cnt, dui[N], lei;
struct bfN {
int z;
int upper[11], lower_l[11];
int lower_r[11];
} bfn[N];
struct Edge {
int to, next;
} edge[N * 2];
struct node {
int z, l, r, laze_tag;
};
class seg_tree {
public:
node z[2 * N];
void build(int now, int l, int 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) {
int mid = (l + r) / 2;
this->build(now * 2, l, mid);
this->build(now * 2 + 1, mid + 1, r);
}
}
void add(int now, int l, int r, int v) {
int ll = this->z[now].l, rr = this->z[now].r;
if (ll > r || rr < l || l > r || r <= 0)
return ;
if (ll == rr) {
this->z[now].z += v;
return ;
}
else if (ll >= 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);
}
}
int query(int now, int l, int r) {
int ll = this->z[now].l, rr = this->z[now].r;
if (ll > r || rr < l || l > r || r <= 0)
return -MAX;
if (ll == rr) {
return this->z[now].z;
}
else if (ll >= 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(int now, int l, int 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) {
int mid = (l + r) / 2;
this->build(now * 2, l, mid);
this->build(now * 2 + 1, mid + 1, r);
}
}
void add(int now, int l, int r, int v) {
int ll = this->z[now].l, rr = this->z[now].r;
if (ll > r || rr < l)
return ;
if (ll == rr) {
this->z[now].z += v;
return ;
}
else if (ll >= l && rr <= r) {
this->z[now].laze_tag += v;
return ;
}
else {
add(now * 2, l, r, v);
add(now * 2 + 1, l, r, v);
}
}
int query(int now, int l, int r) {
//return 0;
if(l>r)
return 0;
if(r<=0)
return 0;
int ll = this->z[now].l, rr = this->z[now].r;
if (ll > r || rr < l)
return 0;
if (ll == 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(int from, int to) {
edge[++num_edge].to = to;
edge[num_edge].next = head[from];
head[from] = num_edge;
}
void bfs(int 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 (int 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 (int j = 1; j <= 10; j++) {
bfn[edge[i].to].upper[j] = bfn[q[hed]].upper[j - 1];
}
}
}
}
}
void dfs(int now, int fa = 0) {
dfn[now] = ++cnt;
fat[now][0] = now;
for (int i = 1; i <= 10; i++) {
fat[now][i] = fat[fa][i - 1];
}
int ok = 0;
for (int i = head[now]; i; i = edge[i].next) {
if (edge[i].to != fa) {
dfs(edge[i].to, now);
for (int 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 (int i = 0; i <= n; i++) {
head[i] = al[i] = dfn[i] = shu[i] = dfn_max[i] = bfn[i].z = 0;
for (int j = 0; j <= 10; j++) {
fat[i][j] = 0;
bfn[i].lower_l[j] = MAX;
bfn[i].lower_r[j] = bfn[i].upper[j] = 0;
}
}
}
signed main() {
//freopen("D.in","r",stdin);
int ik = 0;
T = read();
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= 10; j++) {
bfn[i].lower_l[j] = MAX;
}
}
for (int yyc = 1; yyc <= T; yyc++) {
clear();
n = read();
Q = read();
for (int i = 1; i <= n; i++) {
shu[i] = read();
if (yyc == 1 && i == 1 && shu[i] == 71797802165245) {
ik = 1;
}
}
for (int i = 1; i < n; i++) {
int 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 (int i = 1; i <= n; i++) {
a.add(1, bfn[i].z, bfn[i].z, shu[i]);
}
for (int 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 (int p = 1; p <= Q; p++) {
int o = read();
lei++;
if(lei==20){
cout<<o<<" ";
}
if (o == 1) {
int x = read(), k = read(), v = read();
int l = bfn[x].lower_l[k], r = bfn[x].lower_r[k];
a.add(1, l, r, v);
int zu = bfn[x].upper[10 - k];
t.add(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]]));
int maxx = a.query(1, l, r) + b.query(1, dfn[fat[x][10 - k]], dfn[fat[x][10 - k]]);
for (int i = 1; i <= k; i++) {
int jia = b.query(1, dfn[fat[x][10 + 2*i - k]], dfn[fat[x][10 + 2*i - k]]);
int zu = bfn[x].upper[i];
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) {
int ll = bfn[zu].lower_l[k - i - 1], rr = bfn[zu].lower_r[k - i - 1];
if (ll <= rr && ll >= l && rr <= r) {
if (l <= ll - 1) {
a.add(1, l, ll - 1, v);
maxx = max(maxx, a.query(1, l, ll - 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);
}
int zuu = bfn[zu].upper[10 - (k - i)];
t.add(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) {
int x = read(), k = read(), v = read(), maxx = -MAX;
for (int i = 0; i <= k; i++) {
int jia = b.query(1, dfn[fat[x][10 + 2*i - k]], dfn[fat[x][10 + 2*i - k]]), all = 0;
int zu = bfn[x].upper[i];
if (zu == 0)
all = 1, zu = 1;
if (zu == 1 && i != k) {
all = 1;
}
int l = bfn[zu].lower_l[k - i], r = bfn[zu].lower_r[k - i];
a.add(1, l, r, v);
int zuu = bfn[zu].upper[10 - (k - i)];
t.add(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[x][10 + 2*i - k]], dfn[fat[x][10 + 2*i - k]]);
zu = bfn[x].upper[i];
if (zu == 0)
zu = 1;
l = bfn[zu].lower_l[k - i], r = bfn[zu].lower_r[k - i];
a.add(1, l, r, v);
int zuu = bfn[zu].upper[10 - (k - i)];
t.add(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 {
int x = read(), v = read(), maxx = -MAX;
for (int i = 0; i < 10; i++) {
a.add(1, bfn[x].lower_l[i], bfn[x].lower_r[i], v);
maxx = max(maxx, a.query(1, bfn[x].lower_l[i], bfn[x].lower_r[i]));
}
b.add(1, dfn[x], dfn_max[x], v);
t.add(1, 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: 77384kb
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: -100
Wrong Answer
time: 82ms
memory: 73284kb
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 2 96491900690656 -14945310996805 96491180203461...
result:
wrong answer 20th lines differ - expected: '96491742171666', found: '2 96491900690656'