QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345135#5020. 举办乘凉州喵,举办乘凉州谢谢喵ANIG0 351ms46196kbC++143.5kb2024-03-06 10:15:342024-03-06 10:15:35

Judging History

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

  • [2024-03-06 10:15:35]
  • 评测
  • 测评结果:0
  • 用时:351ms
  • 内存:46196kb
  • [2024-03-06 10:15:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,mk[N],siz[N],zs[N],d[N],fa[N],dep[N],zd[N],cd[N],rs[N],bk[N],rt,zx[N],sm[N],mx,MX,jl[N];
vector<int>p[N];
vector<pair<int,int> >g[N];
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];
        if(zd[c]+1>zd[x])cd[x]=zd[x],zd[x]=zd[c]+1;
        else if(zd[c]+1>cd[x])cd[x]=zd[c]+1;
    }
    mk[x]=0;
}
void dfs2(int x,int y){
    d[x]=y;mk[x]=1;
    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);
    }
}
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)];
     //   cout<<x<<" "<<sm[min(c.first-dep[x],MX)]<<" "<<MX<<endl;
    }
    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){
    if(siz[x]==1){
        for(int i=0;i<g[x].size();i++)rs[g[x][i].second]++;
        return;
    }
    bk[x]=1;MX=0;
    dep[x]=0;
    dfs3(x);
    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];
       // cout<<"r"<<x<<endl;
        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);
    }
}
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);
    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});
    }
    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: 6ms
memory: 27780kb

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:

2546
1004
4981
59
57
3369
3369
1004
4974
1719
59
171
4515
59
4952
4981
4974
1365
4981
1
1004
4780
4974
4974
1
13
4952
4515
59
4864
215
3369
472
1004
59
2546
472
131
13
4780
2546
13
13
4056
4952
171
4780
4974
13
171
13
59
59
1004
4981
3369
13
2546
57
13
4864
171
4952
59
4515
2087
1
4958
9
4056
3369
1...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 351ms
memory: 46196kb

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
69427
2793
181264
91707
182
32495
199183
6399
15975
11640
119051
236
689
15
9532
39
36591
178936
55
45424
193403
90246
3417
949
68
34133
60471
199861
188090
75086
126
1
6
4
3
1
9
61156
199860
199151
155706
196287
192860
53742
51861
179199
428
196282
199989
3613
26
99007
134461
198159
20381
7517
...

result:

wrong answer 2nd numbers differ - expected: '69428', found: '69427'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 284ms
memory: 45220kb

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:

12
100250
189419
1417
83887
199124
1908
83887
17
4321
12
4
71
199516
1
181342
71
197305
197305
4321
169235
192649
20
189419
77114
71
195121
170564
109022
100
199516
86
12
194525
354
14548
109022
199516
354
152872
169235
197305
10704
38072
54937
181342
100250
71
11
354
181342
132537
10574
181342
1995...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%