QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743855#7767. 数据结构Larunatrecy35 854ms176592kbC++146.3kb2024-11-13 20:11:092024-11-13 20:11:09

Judging History

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

  • [2024-11-13 20:11:09]
  • 评测
  • 测评结果:35
  • 用时:854ms
  • 内存:176592kb
  • [2024-11-13 20:11:09]
  • 提交

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,%llu]\n",l,r,v);
    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)
{
    S.clear();
    for(int d=0;d<=3;d++)
    {
        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);
        lstx=top[x];
        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));
        lstx=top[x];
        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()
{
     //freopen("a.in", "r", stdin);
    // freopen("a.ans", "w", stdout);
    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);
  //  for(int i=1;i<=n;i++)cout<<seq[i]<<' ';cout<<endl;
    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: 27ms
memory: 64652kb

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:

35336657552
2132878161772
2793855794976
1306497872444
1693875626486
2678446695840
6685676093478
2084626055471
5784606669185
2186592622
4013527305789
1674542130
6524658548
7090320549958
10053627774655
11581742163173
492570862
3336075291054
2834694279
4192678886864
4395772262
4221137767
9630829210
990...

result:

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

Subtask #2:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 672ms
memory: 136584kb

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: 753ms
memory: 142820kb

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: 311ms
memory: 176592kb

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
134314856591137
38210069287857
75886873450233
25202593262786
179527075749107
75824464805181
156951562087927
246509451502559
251383027605191
181645871493459
285463135579296
213791475267931
244907188023273
53374870495674
449509895460
379318070610757
720757882430057
768645037377274
224740893130029
18...

result:

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

Subtask #4:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 685ms
memory: 136680kb

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: 476ms
memory: 154488kb

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: 714ms
memory: 143040kb

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: 726ms
memory: 136700kb

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: '1422571281'

Subtask #6:

score: 0
Skipped

Dependency #4:

100%
Accepted

Dependency #5:

0%

Subtask #7:

score: 15
Accepted

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Test #17:

score: 15
Accepted
time: 854ms
memory: 136688kb

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
12712803164
0
0
8193968417
14426787309
12950092190
0
32958618613
26764906955
8493139167
0
42785505564
55243799113
0
0
0
0
0
16857343623
27991363871
14151995536
55690427136
85838206842
0
26020925273
22490232861
0
0
1662166464
24948089565
0
26561191640
202942896717
0
91771091757
152033022013
2500525...

result:

ok 100098 numbers

Test #18:

score: 15
Accepted
time: 840ms
memory: 129264kb

input:

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

output:

1506
2433795
1964764
29809
23904
32308
3956297
23683
26194
24496
0
5108618
44498
10494148
1493614
8948
11034059
10983525
9340774
68288
15623342
65908
14673691
63760
62016
68610
3785842
68409
71500
4760847
1843709
83560
86276
3800228
24415019
102280
92867
17894104
25995202
96677
14391781
110124
12872...

result:

ok 99928 numbers

Test #19:

score: 15
Accepted
time: 811ms
memory: 148164kb

input:

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

output:

0
6432
5572
2146
5686
15024
5924
10437
10836
16481
12732
37909
15933
53994
38493
121364
89269
36850
69524
53517
239542
137860
93122
118688
151902
9279
120973
73158
28901
122575
43850
21781
119189
28818
71155
127221
157054
65948
40570
183418
150579
145757
147361
89223
4664
78041
329787
100673
50134
6...

result:

ok 100068 numbers

Subtask #8:

score: 0
Skipped

Dependency #1:

0%