QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#588053#9373. Query on TreetosaniaWA 1601ms102676kbC++1412.6kb2024-09-24 23:58:082024-09-24 23:58:08

Judging History

你现在查看的是最新测评结果

  • [2024-09-24 23:58:08]
  • 评测
  • 测评结果:WA
  • 用时:1601ms
  • 内存:102676kb
  • [2024-09-24 23:58:08]
  • 提交

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'