QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742796#7767. 数据结构Larunatrecy0 613ms154644kbC++146.0kb2024-11-13 17:20:112024-11-13 17:20:16

Judging History

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

  • [2024-11-13 17:20:16]
  • 评测
  • 测评结果:0
  • 用时:613ms
  • 内存:154644kb
  • [2024-11-13 17:20:11]
  • 提交

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;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;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: 13ms
memory: 62120kb

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:

4657223527540
3525260662034
2793343744484
1470432607898
3033666321694
2677934645348
6683382085629
10253617780362
5784732544789
2186592622
4013940978092
1674542130
6524658548
7090115254775
10065755562036
11578510707076
492570862
6857297323516
2834694279
9178745909016
4395772262
4221137767
9630829210
...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 613ms
memory: 121892kb

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
2964794112
5224818790
9459319003
13717923473
8673060864
0
11610197664
0
0
9587792729
0
0
0
6539544474
12425650803
0
0
11191496476
0
37597503993
0
0
15164651949
14868775382
34958369318
0
16391028892
0
15726757336
0
2421390...

result:

wrong answer 18th numbers differ - expected: '1424960716', found: '2964794112'

Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 271ms
memory: 154644kb

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
279645312549370
48205939924874
179526731139183
75824457254155
156951554536901
246509099341609
251382675444241
181645863942433
285463128028270
213786734389331
257640861525693
67958670336098
12702704525748
966928739123061
720756746262595
768643901209812
224740493575747...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 578ms
memory: 121656kb

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:

wrong answer 162nd numbers differ - expected: '0', found: '549330330'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #2:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%