QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410099#5020. 举办乘凉州喵,举办乘凉州谢谢喵grass8cow0 563ms137560kbC++174.5kb2024-05-13 12:48:142024-05-13 12:48:15

Judging History

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

  • [2024-05-13 12:48:15]
  • 评测
  • 测评结果:0
  • 用时:563ms
  • 内存:137560kb
  • [2024-05-13 12:48:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
#define pb push_back
const int N=2e5+10;
vector<int>g[N];
namespace Dia{
    bool vis[N];
    int di[25][N],F[N],dk[N];
    int ae[N*25];
    int al[N],ar[N],bl[N],br[N],cn;
    int sz[N],rt,Mx,S;
    void df(int x,int f){
        sz[x]=1;int mm=-1;
        for(int v:g[x])
            if(v!=f&&!vis[v])df(v,x),mm=max(mm,sz[v]),sz[x]+=sz[v];
        mm=max(mm,S-sz[x]);if(mm<Mx)Mx=mm,rt=x;
    }
    int T1[N],T2[N],md1,md2;
    int O,oe;
    void dfs2(int x,int d,int f){
        oe++;
        di[O][x]=d;
        while(md1<d)md1++,T1[md1]=0;
        while(md2<d)md2++,T2[md2]=0;
        T1[d]++,T2[d]++;
        for(int v:g[x])
            if(v!=f&&!vis[v])dfs2(v,d+1,x),sz[x]+=sz[v];
    }
    int fz[N];
    void sol(int x){
        vis[x]=1,O=dk[x];
        T1[0]=(x<=n),md1=0;
        for(int v:g[x])if(!vis[v]){
            T2[0]=0,md2=0;
            oe=0,dfs2(v,1,0);
            for(int i=1;i<=md2;i++)T2[i]+=T2[i-1];
            S=oe,Mx=S+1,df(v,0);
            F[rt]=x,dk[rt]=dk[x]+1,fz[v]=rt;
            bl[rt]=cn+1,br[rt]=cn+md2+1;
            for(int i=0;i<=md2;i++)ae[++cn]=T2[i];
        }
        for(int i=1;i<=md1;i++)T1[i]+=T1[i-1];
        al[x]=cn+1,ar[x]=cn+md1+1;
        for(int i=0;i<=md1;i++)ae[++cn]=T1[i];
        for(int v:g[x])if(!vis[v])sol(fz[v]);
    }
    int oi[N],fp[N];
    int Ask(int x,int d){
        if(d<0)return 0;
        int u=x,su=0,nx=0;
        while(u){
            int oi=di[dk[u]][x];
            if(oi<=d){
                su+=ae[min(ar[u],al[u]+d-oi)];
                if(nx)su-=ae[min(br[nx],bl[nx]+d-oi)];
            }
            nx=u,u=F[u];
        }
        return su;
    }
    void build(){
        oe=cn=0;
        for(int i=1;i<=n;i++)T1[i]=T2[i]=oi[i]=fp[i]=dk[i]=ae[i]=al[i]=ar[i]=bl[i]=br[i]=F[i]=dk[i]=0,vis[i]=0;
        S=n,Mx=n+1,df(1,0),sol(rt);
    }
}
int sz[201000],son[201000],dfn[201000],top[200100],db[200100],bel[200100],fa[201000],d[201000];
void dfs(int x){
    sz[x]=1;int mm=-1;
    for(int v:g[x])if(v!=fa[x]){
        fa[v]=x,d[v]=d[x]+1,dfs(v);
        if(mm<sz[v])mm=sz[v],son[x]=v;
    }
}
void dfs2(int x,int ff){
    bel[dfn[x]=++dfn[0]]=x,top[x]=ff;
    if(!son[x]){db[x]=x;return;}
    dfs2(son[x],ff),db[x]=db[son[x]];
    for(int v:g[x])if(v!=fa[x]&&v!=son[x])dfs2(v,v);
}
int lca(int u,int v){
    if(top[u]!=top[v]){
        if(d[top[u]]<d[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    if(d[u]>d[v])swap(u,v);return u;
}
struct BIT{
    int tr[201000];
    bool vis[201000];
    int sta[200100],top;
    inline void ad(int x,int z){
        for(x++;x<=n+1;x+=(x&-x)){
            if(!vis[x])vis[x]=1,sta[++top]=x;
            tr[x]+=z;
        }
    }
    inline int ask(int x){
        if(x<0)return 0;
        x=min(x,n);
        int s=0;
        for(x++;x;x-=(x&-x))s+=tr[x];
        return s;
    }
    inline void cl(){
        while(top)vis[sta[top]]=0,tr[sta[top]]=0,top--;
    }
}T;
int ans[200100];
vector<array<int,3> >G[200100];
void sg(int u,int d,int id,int z){
    while(u)
        G[u].pb({d,id,z}),u=fa[top[u]];
}
void sol(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)g[i].clear(),sz[i]=son[i]=dfn[i]=top[i]=db[i]=bel[i]=fa[i]=d[i]=0,G[i].clear();
    for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),g[u].pb(v),g[v].pb(u);
    Dia::build();
    dfn[0]=0,dfs(1),dfs2(1,1);
    int q;
    scanf("%d",&q);
    for(int i=1,u,v,d;i<=q;i++){
        scanf("%d%d%d",&u,&v,&d);
        int lc=lca(u,v);
        ans[i]=Dia::Ask(lc,d);
        sg(u,d,i,1),sg(v,d,i,1),sg(lc,d,i,-2);
    }
    for(int t=1;t<=n;t++)if(top[t]==t){
        for(int j=dfn[t];j<=dfn[db[t]];j++){
            int u=bel[j];
            T.ad(0,1),T.ad(d[u]-d[t]+1,-1);
            if(son[u]){
                for(int k=dfn[son[u]]+sz[son[u]];k<dfn[u]+sz[u];k++){
                    int z=d[bel[k]]-d[u];
                    T.ad(z,1),T.ad(z+1+(d[u]-d[t]),-1);
                }
            }
            for(auto it:G[u])ans[it[1]]+=T.ask(it[0])*it[2];
        }
        T.cl();
        for(int j=dfn[db[t]];j>dfn[t];j--){
            int u=bel[j];
            T.ad(d[u]-d[t],1);
            if(son[u]){for(int k=dfn[son[u]]+sz[son[u]];k<dfn[u]+sz[u];k++)T.ad(d[bel[k]]-d[t],1);}
            for(auto it:G[fa[u]])
            ans[it[1]]+=(T.ask(it[0]+(d[u]-d[t]-1))-T.ask(it[0]-1))*it[2];
        }
        T.cl();
    }
    for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}
int main(){
    int T=1;while(T--)sol();
    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: 7ms
memory: 43192kb

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:

619
57
2849
30
11
119
94
48
3397
119
15
92
1183
17
3369
3593
3515
115
4197
4
172
1069
4083
4032
3
10
1573
694
8
1306
24
791
164
76
18
467
22
51
11
1727
111
6
11
206
2655
31
1737
2330
6
31
7
19
13
11
4197
236
6
327
9
14
3980
12
4100
13
2058
430
3
2593
8
1620
504
11
487
29
14
1209
141
2182
4618
2478
2...

result:

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

Subtask #2:

score: 0
Runtime Error

Test #9:

score: 8
Accepted
time: 491ms
memory: 114424kb

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: 8
Accepted
time: 456ms
memory: 137560kb

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
Accepted
time: 563ms
memory: 91416kb

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:

97095
57496
116181
132482
144412
69917
174677
96334
37980
80902
148979
22074
166530
153392
43419
163281
148526
62703
79363
199993
153733
152298
5085
156125
117973
61925
36346
95741
124148
102890
20093
5408
77598
176994
177809
169850
144418
43786
189237
69098
5167
199993
103575
105198
197612
38829
20...

result:

ok 199994 numbers

Test #12:

score: 0
Runtime Error

input:

200000
3219 118490
118490 61372
61372 74390
74390 88375
88375 63918
63918 37580
37580 33219
33219 170480
170480 81737
81737 153202
153202 93921
93921 149109
149109 88339
88339 167037
167037 67099
67099 58363
58363 6784
6784 109386
109386 11895
11895 14872
14872 65638
65638 43958
43958 181669
181669 ...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 542ms
memory: 113992kb

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:

8
20452
63744
32
624
124364
54
13274
8
77
13
7
15
140913
3
12418
10
88231
114283
106
4014
70020
4
8380
744
11
98871
30889
962
33
91478
24
8
66981
12
53
14258
155478
25
29850
22798
95065
247
470
190
34304
1657
16
12
18
5061
1645
642
84225
154366
39
552
2994
11
80180
16468
356
11469
144290
76357
20639...

result:

wrong answer 1st numbers differ - expected: '78', found: '8'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%