QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345162#5020. 举办乘凉州喵,举办乘凉州谢谢喵ANIG0 1103ms162504kbC++146.2kb2024-03-06 11:51:352024-03-06 11:51:36

Judging History

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

  • [2024-03-06 11:51:36]
  • 评测
  • 测评结果:0
  • 用时:1103ms
  • 内存:162504kb
  • [2024-03-06 11:51:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
struct trs{
    struct node{
        int lson,rson,sm;
    }p[N*20];
    void upset(int x){
        p[x].sm=p[p[x].lson].sm+p[p[x].rson].sm;
    }
    int idx;
    void add(int x,int y,int d,int sm,int nl=0,int nr=2e5){
        if(nl==nr){
            p[y].sm=p[x].sm+sm;
            return;
        }
        int mid=nl+nr>>1;
        if(d<=mid){
            p[y].lson=++idx;p[y].rson=p[x].rson;
            add(p[x].lson,idx,d,sm,nl,mid);
        }else{
            p[y].rson=++idx;p[y].lson=p[x].lson;
            add(p[x].rson,idx,d,sm,mid+1,nr);
        }
        upset(y);
    }
    int gets(int x,int l,int r,int nl=0,int nr=2e5){
        if(!x||l>r)return 0;
        if(l<=nl&&r>=nr)return p[x].sm;
        int mid=nl+nr>>1;
        if(r<=mid)return gets(p[x].lson,l,r,nl,mid);
        if(l>mid)return gets(p[x].rson,l,r,mid+1,nr);
        return gets(p[x].lson,l,r,nl,mid)+gets(p[x].rson,l,r,mid+1,nr);
    }
}tr;
int idx,ts[N],gn[N],qz[N],n,m,mk[N],siz[N],zs[N],d[N],fa[N],dep[N],rs[N],bk[N],rt,zx[N],sm[N],mx,MX,jl[N],dfn[N],eds[N],dy[N],dp[N];
vector<int>p[N],f[N];
vector<pair<int,int> >g[N];
void dfs7(vector<int>&f,int x,int y){
    f[dep[x]-dep[y]]++;mk[x]=1;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c])continue;
        dfs7(f,c,y);
    }
    mk[x]=0;
}
void dfs1(int x){
    mk[x]=1;siz[x]=1;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c])continue;
        fa[c]=x;
        dep[c]=dep[x]+1;
        dfs1(c);
        if(siz[c]>siz[zs[x]])zs[x]=c;
        siz[x]+=siz[c];
    }
    int sz=0;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c]||c==zs[x])continue;
        sz=max(sz,siz[c]);
    }
    f[x].resize(sz+1);
    f[x][0]=1;
    for(int i=1;i<f[x].size();i++)f[x][i]+=f[x][i-1];
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c]||c==zs[x])continue;
        dfs7(f[x],c,x);
    }
    mk[x]=0;
}
void dfs2(int x,int y){
    d[x]=y;mk[x]=1;dfn[x]=++idx;dy[idx]=x;
    dp[x]=dep[x]-dep[y];
    if(zs[x])dfs2(zs[x],y);
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c])continue;
        dfs2(c,c);
    }
    eds[x]=idx;
}
int lca(int a,int b){
    while(d[a]!=d[b]){
        if(dep[d[a]]>dep[d[b]])swap(a,b);
        b=fa[d[b]];
    }
    if(dep[a]>dep[b])swap(a,b);
    return a;
}
void dfs3(int x){
    MX=max(MX,dep[x]);
    mk[x]=1;siz[x]=1;sm[dep[x]]++;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c]||bk[c])continue;
        dep[c]=dep[x]+1;
        dfs3(c);
        siz[x]+=siz[c];
    }
    mk[x]=0;
}
void dfs4(int x,int y){
    mk[x]=1;zx[x]=0;siz[x]=1;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c]||bk[c])continue;
        dfs4(c,y);
        siz[x]+=siz[c];
        zx[x]=max(zx[x],siz[c]);
    }
    zx[x]=max(zx[x],y-siz[x]);
    mk[x]=0;
    if(!rt||zx[rt]>zx[x])rt=x;
}
void dfs5(int x){
    mk[x]=1;mx=max(mx,dep[x]);jl[dep[x]]++;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(bk[c]||mk[c])continue;
        dep[c]=dep[x]+1;
        dfs5(c);
    }
    mk[x]=0;
}
void dfs6(int x){
    mk[x]=1;
    for(int i=0;i<g[x].size();i++){
        auto c=g[x][i];
        if(dep[x]>c.first)continue;
        rs[c.second]+=sm[min(c.first-dep[x],MX)]-jl[min(c.first-dep[x],mx)];
    }
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(bk[c]||mk[c])continue;
        dfs6(c);
    }
    mk[x]=0;
}
void solve(int x){
    bk[x]=1;MX=0;
    dep[x]=0;
    dfs3(x);
    if(siz[x]==1){
        for(int i=0;i<g[x].size();i++)rs[g[x][i].second]++;
        sm[0]=0;
        return;
    }
    for(int i=1;i<=MX;i++)sm[i]+=sm[i-1];
    for(int i=0;i<g[x].size();i++)rs[g[x][i].second]+=sm[min(g[x][i].first,MX)];
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(bk[c])continue;
        dep[c]=1;mx=0;
        dfs5(c);
        for(int j=1;j<=mx;j++)jl[j]+=jl[j-1];
        dfs6(c);
        for(int j=0;j<=mx;j++)jl[j]=0;
    }
    for(int i=0;i<=MX;i++)sm[i]=0;
    for(int i=0;i<p[x].size();i++){
        int c=p[x][i];
        if(bk[c])continue;
        rt=0;
        dfs4(c,siz[c]);
        solve(rt);
    }
}
int gets(int x,int l,int r){
    return tr.gets(gn[eds[x]],dep[x]+l,dep[x]+r)-tr.gets(gn[dfn[x]-1],dep[x]+l,dep[x]+r);
}
struct ask{
    int k,op,bh;
};
vector<ask>gs[N];
int solve(int x,int k,int bh,int op){
    int res=0;
    while(x){
        if(zs[x])res+=gets(zs[x],max(k-dep[x]-1,0ll),k-1);
      //  gs[dfn[d[x]]-1].push_back({k,-op,bh});
       // gs[dfn[x]].push_back({k,op,bh});
        for(int i=dfn[d[x]];i<=dfn[x];i++){
            res+=f[dy[i]][min(k,(int)f[dy[i]].size()-1)];
            if(k>dp[dy[i]])res-=f[dy[i]][min(k-dp[dy[i]]-1,(int)f[dy[i]].size()-1)];
          //  cout<<dy[i]<<" "<<res<<endl;
        }
        x=fa[d[x]];
    }
  //  cout<<k<<"-"<<res<<endl;
    return res;
}
signed main(){
  //  freopen("in.txt","r",stdin);
   // freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        p[x].push_back(y);
        p[y].push_back(x);
    }
    dfs1(1);
    dfs2(1,1);
    for(int i=1;i<=n;i++){
        gn[i]=++tr.idx;
        tr.add(gn[i-1],gn[i],dep[dy[i]],1);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        int x,y,k,c;
        cin>>x>>y>>k;
        c=lca(x,y);
        g[c].push_back({k,i});
        rs[i]=solve(x,k,i,1)+solve(y,k,i,1)-solve(c,k,i,-2)*2;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<f[dy[i]].size();j++){
            qz[j]+=f[dy[i]][min((int)f[dy[i]].size()-1,j)];
            if(j>dp[dy[i]])qz[j]-=f[dy[i]][min((int)f[dy[i]].size()-1,j-dp[dy[i]]-1)];
        }
        for(int j=0;j<gs[i].size();j++){
            auto c=gs[i][j];
            rs[c.bh]+=c.op*qz[c.k];
            cout<<i<<" "<<c.bh<<" "<<c.op<<" "<<c.k<<" "<<qz[c.k]<<endl;
        }
    }
    memset(mk,0,sizeof(mk));
    solve(1);
    for(int i=1;i<=m;i++)cout<<rs[i]<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 14ms
memory: 27204kb

input:

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

output:

3018
1208
4983
171
183
3087
3158
1269
4968
2020
245
337
4355
247
4955
4995
4963
1529
4981
12
1412
4870
4966
4974
19
82
4881
4646
172
4857
365
3691
775
1487
177
2947
845
184
84
4861
2847
70
81
4235
4929
450
4529
4968
113
381
75
136
165
1288
4976
3179
100
2969
173
66
4875
393
4897
300
4530
1924
15
495...

result:

wrong answer 1st numbers differ - expected: '3226', found: '3018'

Subtask #2:

score: 0
Time Limit Exceeded

Test #9:

score: 8
Accepted
time: 950ms
memory: 153804kb

input:

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

output:

757
69428
2793
181264
91707
182
32496
199183
6399
15975
11640
119051
236
689
15
9532
41
36592
178936
56
45424
193403
90248
3417
949
68
34133
60471
199861
188090
75088
127
1
6
4
3
3
11
61157
199860
199153
155706
196287
192862
53742
51862
179199
428
196282
199989
3613
26
99007
134461
198159
20382
7518...

result:

ok 199996 numbers

Test #10:

score: 0
Accepted
time: 985ms
memory: 162504kb

input:

199993
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
27 54
2...

output:

22
31743
62
30
510
6079
94
24063
190
4079
382
30
62
12159
1022
2043
8063
62
4
3063
4079
30
254
46
10
22
6111
12159
16127
22
1
12031
1
94
382
766
4063
254
46
766
1022
62
766
1
22
46
30
8063
8063
254
3063
22
62
30
1
62
254
4
10
15871
1022
46
2039
6079
22
254
1022
16127
30
766
8127
14
14
10
46
1
62
406...

result:

ok 199995 numbers

Test #11:

score: -8
Time Limit Exceeded

input:

199993
25163 125238
125238 19096
19096 88864
88864 113505
113505 12722
12722 56225
56225 8736
8736 74926
74926 38529
38529 80231
80231 19719
19719 198784
198784 75213
75213 190174
190174 163340
163340 62363
62363 144160
144160 130912
130912 3919
3919 21218
21218 85281
85281 187312
187312 79930
79930...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 1103ms
memory: 152344kb

input:

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

output:

78
100046
191004
4179
94438
199013
2212
85952
75
9713
149
58
572
199584
25
178211
410
197101
197994
8022
171593
192241
99
189554
78336
410
194887
170964
116880
242
199542
573
142
195779
1930
18427
121390
199929
1827
164333
176048
196917
12528
48164
52799
181434
96180
525
131
1621
175598
126960
16155...

result:

wrong answer 2nd numbers differ - expected: '107329', found: '100046'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%