QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743828#7767. 数据结构Larunatrecy20 897ms176512kbC++146.2kb2024-11-13 20:07:502024-11-13 20:07:57

Judging History

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

  • [2024-11-13 20:07:57]
  • 评测
  • 测评结果:20
  • 用时:897ms
  • 内存:176512kb
  • [2024-11-13 20:07:50]
  • 提交

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);
        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);
    //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: 20ms
memory: 62204kb

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:

36872809028
2133390212264
2793855794976
1307009922936
1694899727470
2678446695840
6688109198931
2084626055471
5786458114775
2186592622
4015378751379
1674542130
6524658548
7092503166335
10056846008752
11584531057011
492570862
3336681568515
2834694279
4192678886864
4395772262
4221137767
9630829210
991...

result:

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

Subtask #2:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 773ms
memory: 136900kb

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: 838ms
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: 351ms
memory: 176512kb

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

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: 501ms
memory: 154540kb

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: 781ms
memory: 143124kb

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: 810ms
memory: 136712kb

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: 0
Wrong Answer

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Test #17:

score: 0
Wrong Answer
time: 897ms
memory: 136876kb

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%