QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743798#7767. 数据结构Larunatrecy20 767ms154640kbC++146.1kb2024-11-13 20:02:592024-11-13 20:03:00

Judging History

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

  • [2024-11-13 20:03:00]
  • 评测
  • 测评结果:20
  • 用时:767ms
  • 内存:154640kb
  • [2024-11-13 20:02:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
    x=0;char c=getchar();bool f=0;
    for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
    x=(f?-x:x);
}
typedef unsigned long long ull;
const int N = 2e5+7;
typedef long long LL;
int n;
vector<int> G[N],T[N];
int fa[N],siz[N],son[N],dfn[N],dep[N],top[N],seq[N],tot=0;
void dfs(int x,int pre)
{
    fa[x]=pre;siz[x]=1;dep[x]=dep[pre]+1;
    for(int y:T[x])if(y!=pre)
    {
        dfs(y,x);
        siz[x]+=siz[y];
        G[x].push_back(y);
        if(siz[y]>siz[son[x]])son[x]=y;
    }
}
struct BIT
{
    ull d[N],c[N];
    void add1(int x,ull v){for(int i=x;i<=n+1;i+=i&-i)d[i]+=v;}
    void add2(int x,ull v){for(int i=x;i<=n+1;i+=i&-i)c[i]+=v;}
    ull ask1(int x){ull res=0;for(int i=x;i;i-=i&-i)res+=d[i];return res;}
    ull ask2(int x){ull res=0;for(int i=x;i;i-=i&-i)res+=c[i];return res;}
    inline ull sum(int x){return ask1(x)*(x+1)-ask2(x);}
    inline void add(int l,int r,ull v)
    {if(l>r)return;//printf("add:[%d,%d]\n",l,r);
    add1(l,v);add1(r+1,-v);add2(l,v*l);add2(r+1,-v*(r+1));}
    inline ull ask(int l,int r)
    {
        if(l>r)return 0;//printf("ask:[%d,%d]\n",l,r);
    return sum(r)-sum(l-1);}
}DS;
void extend(int x,int t)
{
    if(!dfn[x])seq[dfn[x]=++tot]=x;
    if(!t)return;
    for(int y:G[x])extend(y,t-1);
}
void dfs2(int x,int topth)
{
    top[x]=topth;
    if(x==topth)
    {
        for(int i=0;i<=3;i++)
        for(int u=x;u;u=son[u])extend(u,i);
    }
    if(!son[x])return;
    dfs2(son[x],topth);
    for(int y:G[x])if(y!=fa[x]&&y!=son[x])dfs2(y,y);
}
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define l(x) x.first
#define r(x) x.second
#define segment vector<pii>
segment operator +(segment A,segment B)
{
    if(A.empty())return B;
    if(B.empty())return A;
    segment C;
    int i=0,j=0,l=-1;
    while(i<(int)A.size()||j<(int)B.size())
    {
        pii cur;
        if(j>=(int)B.size()||(i<(int)A.size()&&A[i].first<B[j].first))
        cur=A[i++];
        else cur=B[j++];
        if(l(cur)==l+1)C.back().second=cur.second;
        else C.push_back(cur);
        l=cur.second;
    }
    return C;
}
segment tree[N];
void dfs3(int x,int pre)
{
    tree[x].push_back(mk(dfn[x],dfn[x]));
    for(int y:G[x])
    {
        dfs3(y,x);
        tree[x]=tree[x]+tree[y];
    }
}
segment A[N][4],W[N][4];
bool vis[N];
segment S;
void get(int x,int d)
{
    segment cur;cur.push_back({dfn[x],dfn[x]});
    if(!d){S=S+cur;return;}
    for(int y:G[x])if(!vis[y])get(y,d-1);
}
void dfs4(int x)
{
    for(int d=0;d<=3;d++)
    {
        S.clear();
        get(x,d);
        W[x][d]=S;
    }
    if(x==top[x])
    {
        for(int u=x;u;u=son[u])vis[u]=1;
        for(int d=0;d<=3;d++)
        {
            S.clear();
            for(int u=x;u;u=son[u])
            {
                get(u,d);
                if(d)A[u][d]=A[u][d-1];
                A[u][d]=A[u][d]+S;
            }
        }
        for(int u=x;u;u=son[u])vis[u]=1;
    }
    if(!son[x])return;
    dfs4(son[x]);
    for(int y:G[x])if(y!=son[x])
    dfs4(y);
}
void apply(int x,int k,ull v)
{
    int lst=x;
    for(int i=1;i<=k;i++)
    {
        lst=x;
        x=fa[x];
        if(!x)return;
        for(auto u:W[x][k-i])DS.add(l(u),r(u),v);
        if(i<k)for(auto u:W[lst][k-i-1])DS.add(l(u),r(u),-v);
    }
}
void modify(int x,int y,int k,int v)
{
    int lstx=0,lsty=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y),swap(lstx,lsty);
        for(auto u:A[x][k])DS.add(l(u),r(u),v);
        if(lstx&&k)for(auto u:W[lstx][k-1])DS.add(l(u),r(u),-v);
        if(son[x]&&k)for(auto u:W[son[x]][k-1])DS.add(l(u),r(u),v);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y),swap(lstx,lsty);
    for(auto u:A[y][k])DS.add(l(u),r(u),v);
    if(x!=top[x])
    for(auto u:A[fa[x]][k])DS.add(l(u),r(u),-v);
    if(lstx&&k)for(auto u:W[lstx][k-1])DS.add(l(u),r(u),-v);
    if(lsty&&k)for(auto u:W[lsty][k-1])DS.add(l(u),r(u),-v);
    if(son[y]&&k)for(auto u:W[son[y]][k-1])DS.add(l(u),r(u),v);
    if(k)apply(x,k,v);
}
ull getans(int x,int k)
{
    ull res=0;
    int lst=x;
    for(int i=1;i<=k;i++)
    {
        lst=x;
        x=fa[x];
        if(!x)break;
        for(auto u:W[x][k-i])res+=DS.ask(l(u),r(u));
        if(i<k)for(auto u:W[lst][k-i-1])res-=DS.ask(l(u),r(u));
    }
    return res;
}
ull query(int x,int y,int k)
{
    ull res=0;
    int lstx=0,lsty=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y),swap(lstx,lsty);
        for(auto u:A[x][k])res+=DS.ask(l(u),r(u));
        if(lstx&&k)for(auto u:W[lstx][k-1])res-=DS.ask(l(u),r(u));
        if(son[x]&&k)for(auto u:W[son[x]][k-1])res+=DS.ask(l(u),r(u));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y),swap(lstx,lsty);
    for(auto u:A[y][k])res+=DS.ask(l(u),r(u));
    if(x!=top[x])
    for(auto u:A[fa[x]][k])res-=DS.ask(l(u),r(u));
    if(lstx&&k)for(auto u:W[lstx][k-1])res-=DS.ask(l(u),r(u));
    if(lsty&&k)for(auto u:W[lsty][k-1])res-=DS.ask(l(u),r(u));
    if(son[y]&&k)for(auto u:W[son[y]][k-1])res+=DS.ask(l(u),r(u));
    if(k)res+=getans(x,k);
    return res;
}
int main()
{
    int m;
    read(n);read(m);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u);read(v);
        T[u].push_back(v);
        T[v].push_back(u);
    }
    dfs(1,0);dfs2(1,1);
    dfs3(1,0);dfs4(1);
    while(m--)
    {
        int op,x,y,k,v;
        read(op);
        if(op==1)
        {
            read(x);read(y);read(k);read(v);
            modify(x,y,k,v);
        }
        else if(op==2)
        {
            read(x);read(v);
            for(auto u:tree[x])DS.add(l(u),r(u),v);
        }
        else if(op==3)
        {
            read(x);read(y);read(k);
            printf("%lld\n",query(x,y,k));
        }
        else if(op==4)
        {
            read(x);
            ull res=0;
            for(auto u:tree[x])res+=DS.ask(l(u),r(u));
            printf("%lld\n",res);

        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 17ms
memory: 62144kb

input:

5000 5000
1 2
2 3
3 4
4 5
5 6
5 7
6 8
7 9
9 10
8 11
11 12
12 13
12 14
14 15
15 16
16 17
16 18
18 19
18 20
20 21
20 22
22 23
23 24
23 25
23 26
26 27
27 28
28 29
27 30
30 31
29 32
32 33
33 34
32 35
35 36
36 37
35 38
36 39
38 40
38 41
41 42
42 43
43 44
42 45
44 46
45 47
47 48
48 49
48 50
49 51
51 52
52...

output:

34981763088
2131932638802
2793343744484
1305552349474
1692496631038
2677934645348
6683382085629
2081426057982
5784732544789
2186592622
4013940978092
1674542130
6524658548
7090115254775
10048023011004
11578510707076
492570862
3325092033836
2834694279
4189252521026
4395772262
4221137767
9630829210
991...

result:

wrong answer 1st numbers differ - expected: '37227703492', found: '34981763088'

Subtask #2:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 647ms
memory: 121608kb

input:

200000 200000
1 2
1 3
1 4
3 5
1 6
1 7
7 8
8 9
2 10
1 11
5 12
1 13
7 14
10 15
2 16
7 17
11 18
5 19
5 20
1 21
16 22
1 23
3 24
20 25
14 26
2 27
6 28
15 29
10 30
15 31
5 32
13 33
12 34
31 35
31 36
36 37
36 38
1 39
28 40
5 41
12 42
41 43
20 44
30 45
22 46
11 47
47 48
45 49
14 50
41 51
3 52
30 53
29 54
6 ...

output:

0
0
0
0
0
0
0
0
7615073807
4176911055
0
4745654848
6222845818
0
0
9739142819
0
1424960716
5224818790
9459319003
13717923473
8673060864
0
11610197664
0
0
9587792729
0
0
0
2747489046
12425650803
0
0
11191496476
0
37597503993
0
0
15164651949
14868775382
15559673116
0
16391028892
0
15726757336
0
2421390...

result:

ok 100169 numbers

Test #4:

score: 10
Accepted
time: 700ms
memory: 128144kb

input:

200000 200000
121679 2
13340 3
45206 4
112138 5
47397 6
88216 7
173469 8
109861 9
58662 10
130056 11
61155 12
4313 13
196310 14
46189 15
32349 16
143798 17
103215 18
159921 19
27365 20
14332 21
49504 22
64451 23
106931 24
59878 25
177587 26
100555 27
86848 28
793 29
79845 30
150813 31
42854 32
11551...

output:

77900221111
0
0
476439705914
0
216029652830
0
0
631267909751
508097390689
0
29277716182
695169620128
0
809294022024
0
0
829507748883
260130797154
0
1005527232590
109198360548
821333235719
0
0
1265757368752
738460021055
296232170804
845184728833
0
434366813420
0
1922343637889
0
0
0
229703081048
0
441...

result:

ok 100073 numbers

Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 276ms
memory: 154640kb

input:

200000 200000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 ...

output:

0
134314511981213
38210069287857
75884072418736
25202420957824
179526731139183
75824457254155
156951554536901
246509099341609
251382675444241
181645863942433
285463128028270
213786734389331
244905818158545
53373845240870
448431934080
379302811856289
720756746262595
768643901209812
224740493575747
18...

result:

wrong answer 2nd numbers differ - expected: '134315201201061', found: '134314511981213'

Subtask #4:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 635ms
memory: 121724kb

input:

200000 200000
1 2
2 3
3 4
1 5
3 6
5 7
5 8
7 9
2 10
7 11
11 12
10 13
6 14
3 15
14 16
4 17
11 18
3 19
14 20
4 21
4 22
12 23
18 24
5 25
5 26
14 27
13 28
24 29
11 30
26 31
29 32
28 33
31 34
23 35
33 36
6 37
11 38
22 39
13 40
35 41
37 42
21 43
12 44
4 45
16 46
12 47
21 48
1 49
26 50
45 51
41 52
46 53
7 5...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99786 numbers

Test #8:

score: 10
Accepted
time: 456ms
memory: 138244kb

input:

200000 200000
1 2
2 3
1 4
1 5
2 6
3 7
6 8
8 9
8 10
9 11
8 12
12 13
13 14
11 15
13 16
13 17
16 18
17 19
18 20
19 21
19 22
21 23
21 24
21 25
24 26
23 27
26 28
27 29
26 30
30 31
28 32
29 33
32 34
32 35
33 36
36 37
35 38
38 39
38 40
40 41
39 42
42 43
43 44
41 45
45 46
43 47
45 48
46 49
49 50
50 51
51 52...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100404 numbers

Test #9:

score: 10
Accepted
time: 661ms
memory: 128076kb

input:

200000 200000
166945 2
60190 3
101888 4
154621 5
188595 6
175999 7
140051 8
54071 9
167394 10
54228 11
48270 12
14564 13
25727 14
138072 15
77670 16
77795 17
155644 18
171648 19
94412 20
65323 21
130225 22
6359 23
17410 24
8580 25
142556 26
152863 27
166869 28
115234 29
87099 30
160349 31
98200 32
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99768 numbers

Subtask #5:

score: 0
Wrong Answer

Dependency #4:

100%
Accepted

Test #10:

score: 0
Wrong Answer
time: 647ms
memory: 121628kb

input:

200000 200000
1 2
1 3
2 4
1 5
2 6
2 7
2 8
5 9
3 10
10 11
5 12
4 13
5 14
9 15
11 16
14 17
12 18
13 19
2 20
16 21
3 22
16 23
2 24
7 25
8 26
20 27
21 28
11 29
12 30
4 31
2 32
21 33
14 34
29 35
16 36
21 37
28 38
22 39
27 40
12 41
36 42
32 43
30 44
3 45
43 46
4 47
14 48
44 49
9 50
37 51
20 52
11 53
31 54...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 348th numbers differ - expected: '1896761708', found: '948380854'

Subtask #6:

score: 0
Skipped

Dependency #4:

100%
Accepted

Dependency #5:

0%

Subtask #7:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Test #17:

score: 0
Wrong Answer
time: 767ms
memory: 121708kb

input:

200000 200000
1 2
1 3
3 4
1 5
2 6
3 7
1 8
5 9
6 10
9 11
2 12
8 13
3 14
4 15
12 16
10 17
2 18
2 19
14 20
12 21
9 22
19 23
14 24
3 25
13 26
21 27
11 28
5 29
9 30
13 31
13 32
4 33
6 34
14 35
14 36
31 37
13 38
10 39
4 40
28 41
13 42
14 43
20 44
37 45
8 46
14 47
32 48
21 49
40 50
46 51
20 52
44 53
15 54
...

output:

0
16849806164
0
0
9237014108
14980842797
14547193369
0
34620785077
28582135084
9536184858
0
50602196510
63751565995
0
0
0
0
0
17909528605
29097444027
15784168183
63602284518
103641568247
0
27410235941
24210040197
0
0
1662166464
28413282125
0
28484661570
226875881433
0
100259074982
175344184178
28518...

result:

wrong answer 2nd numbers differ - expected: '12712803164', found: '16849806164'

Subtask #8:

score: 0
Skipped

Dependency #1:

0%