QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#875616#5020. 举办乘凉州喵,举办乘凉州谢谢喵duck_pear0 993ms188308kbC++146.1kb2025-01-29 23:57:102025-01-29 23:57:11

Judging History

This is the latest submission verdict.

  • [2025-01-29 23:57:11]
  • Judged
  • Verdict: 0
  • Time: 993ms
  • Memory: 188308kb
  • [2025-01-29 23:57:10]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define TY int
#define IL inline
#define pb push_back
#define MAXN 200005
#define mod (TY)(1e9+7)
#define INF (TY)(1e9)
#define For(i,a,b) for(TY i=(a);i<=(b);++i)
#define FOR(i,a,b) for(TY i=(a);i<(b);++i)
#define Rof(i,a,b) for(TY i=(a);i>=(b);--i)
#define ROF(i,a,b) for(TY i=(a);i>(b);--i)
IL TY qr(){
    TY u=0,v=1;char ch=getchar();
    while(ch>'9'||ch<'0')v=(ch=='-'?-1:1),ch=getchar();
    while(ch>='0'&&ch<='9')u=(u*10)+(ch-'0'),ch=getchar();
    return u*v;
}IL void qw(TY now){
    if(now<0){putchar('-');now=-now;}
    if(!now){putchar('0');return;}
    if(now>=10)qw(now/10);putchar(now%10+'0');
}IL void qw(TY now,char ch){qw(now);putchar(ch);}
IL bool ischar(char u){return (u>='a'&&u<='z')||(u>='A'&&u<='Z');}
IL char getc(){
    char u=getchar();
    while(!ischar(u))u=getchar();
    return u;
}IL string qs(){
    string s="";char ch=getchar();
    while(!ischar(ch))ch=getchar();
    while(ischar(ch))s+=ch,ch=getchar();
    return s;
}IL void ws(string s){FOR(i,0,s.size())putchar(s[i]);}
IL TY Pow(TY a,TY b){
    TY ans=1,base=a;
    while(b){
        if(b&1)ans=ans*base%mod;
        base=base*base%mod;b>>=1;
    }return ans;
}IL TY Mod(TY u){return (u>=mod?u-mod:u);}
TY n,m,siz[MAXN],deep[MAXN],father[MAXN],son[MAXN],top[MAXN],ans[MAXN],id[MAXN],seg[MAXN],cnt;
TY rt,S,maxx[MAXN];
bool vis[MAXN];
vector<TY> e[MAXN];
struct node{TY d,op,id;};
IL bool cmp(node x,node y){return x.d<y.d;}
vector<node> q1[MAXN],q2[MAXN],q3[MAXN];
IL void Pb(TY i,TY j){e[i].pb(j);e[j].pb(i);}
struct Tree{
    TY tree[MAXN];
    stack<TY> use;
    IL void clear(){
        while(!use.empty())tree[use.top()]=0,use.pop();
    }IL void add(TY now,TY w){
        ++now;
        while(now<=n+1){
            tree[now]+=w;
            use.push(now);
            now+=(now&-now);
        }
    }IL TY query(TY now){
        ++now;
        TY sum=0;
        while(now){
            sum+=tree[now];
            now-=(now&-now);
        }return sum;
    }IL TY query(TY l,TY r){
        if(l>r)return 0;
        else return query(r)-query(l-1);
    }
}tr;
void dfs1(TY now,TY fa){
    TY nowson=-1;
    siz[now]=1;
    deep[now]=deep[fa]+1;
    father[now]=fa;
    FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(y==fa)continue;
        dfs1(y,now);
        siz[now]+=siz[y];
        if(siz[y]>nowson){nowson=siz[y];son[now]=y;}
    }
}void dfs2(TY now,TY topf){
    id[now]=++cnt;
    seg[cnt]=now;
    top[now]=topf;
    if(!son[now])return;
    dfs2(son[now],topf);
    FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(y==father[now]||y==son[now])continue;
        dfs2(y,y);
    }
}TY LCA(TY x,TY y){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        x=father[top[x]];
    }if(deep[x]>deep[y])swap(x,y);
    return x;
}void query(TY u,TY v,TY d,TY id){
    TY z=LCA(u,v);
    if(u!=z)q2[u].pb({d,1,id});
    if(v!=z)q2[v].pb({d,1,id});
    while(top[u]!=top[v]){
        if(deep[top[u]]<deep[top[v]])swap(u,v);
        q1[father[u]].pb({d,1,id});
        q1[father[top[u]]].pb({d,-1,id});
        u=top[u];
        if(father[u]!=z){
            q2[father[u]].pb({d,1,id});
            q2[u].pb({d-1,-1,id});
        }else q2[u].pb({d-1,-1,id});
        u=father[u];
    }if(deep[u]>deep[v])swap(u,v);
    if(u!=v){
        q1[father[v]].pb({d,1,id});
        q1[u].pb({d,-1,id});
        q2[son[u]].pb({d-1,-1,id});
    }q3[z].pb({d,1,id});
}void dfs3(TY now,TY fa){
    vector<TY> have;
    FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(y==fa||y==son[now])continue;
        For(j,id[y],id[y]+siz[y]-1)have.pb(deep[seg[j]]);
    }sort(have.begin(),have.end());
    sort(q1[now].begin(),q1[now].end(),cmp);
    TY tmp=0;
    FOR(i,0,q1[now].size()){
        while(tmp<have.size()&&have[tmp]<=q1[now][i].d)++tmp;
        ans[q1[now][i].id]+=q1[now][i].op*tmp;
    }FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(y==fa)continue;
        dfs3(y,now);
    }
}void dfs4(TY now,TY fa){
    FOR(i,0,q2[now].size()){
        if(q2[now][i].d<0)continue;
        ans[q2[now][i].id]-=q2[now][i].op*tr.query(deep[now],deep[now]+q2[now][i].d);
    }tr.add(deep[now],1);
    FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(y==fa)continue;
        dfs4(y,now);
    }FOR(i,0,q2[now].size()){
        if(q2[now][i].d<0)continue;
        ans[q2[now][i].id]+=q2[now][i].op*tr.query(deep[now],deep[now]+q2[now][i].d);
    }
}void get_siz(TY now,TY fa){
    siz[now]=1;maxx[now]=0;
    FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(y==fa||vis[y])continue;
        get_siz(y,now);
        siz[now]+=siz[y];
        maxx[now]=max(maxx[now],siz[y]);
    }maxx[now]=max(maxx[now],S-siz[now]);
    if(maxx[now]<maxx[rt])rt=now;
}void get_ans(TY now,TY deep,TY fa,TY op){
    if(op==0){
        FOR(i,0,q3[now].size())ans[q3[now][i].id]+=tr.query(0,q3[now][i].d-deep);
    }else tr.add(deep,op);
    FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(y==fa||vis[y])continue;
        get_ans(y,deep+1,now,op);
    }
}void solve(TY now){
    vis[now]=1;
    get_siz(now,0);
    tr.clear();
    tr.add(0,1);
    FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(vis[y])continue;
        get_ans(y,1,now,1);
    }FOR(i,0,q3[now].size())ans[q3[now][i].id]+=tr.query(0,q3[now][i].d);
    FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(vis[y])continue;
        get_ans(y,1,now,-1);
        get_ans(y,1,now,0);
        get_ans(y,1,now,1);
    }FOR(i,0,e[now].size()){
        TY y=e[now][i];
        if(vis[y])continue;
        S=siz[y];rt=0;maxx[rt]=1e9;
        get_siz(y,now);
        solve(rt);
    }
}
int main(){
    n=qr();
    tr.add(0,1);
    cout<<tr.query(0,1)<<endl;
    FOR(i,1,n){
        TY u=qr(),v=qr();
        Pb(u,v);
    }dfs1(1,0);
    dfs2(1,1);
    m=qr();
    For(i,1,m){
        TY u=qr(),v=qr(),d=qr();
        query(u,v,d,i);
    }dfs3(1,0);
    dfs4(1,0);
    solve(1);
    For(i,1,m)qw(ans[i],'\n');
    return 0;
}
/*
6
1 2
2 3
2 4
1 5
4 6
1
2 4 1
 */

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: 28896kb

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:

1
2945
236
-3382
101
93
639
-411
726
85
1435
127
343
407
130
-1047
1432
-2712
1476
2906
7
1119
-711
-1391
1864
8
40
-3298
-687
126
2630
312
558
736
513
147
1826
685
118
45
-257
1567
47
26
1490
-293
144
-1941
244
34
301
48
119
164
278
-15
-702
48
2988
114
35
2065
388
340
91
4624
1801
7
1357
38
1951
9...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 664ms
memory: 78712kb

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:

1
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
75...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 993ms
memory: 188308kb

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:

1
56
57323
170706
2266
51518
123871
1452
76744
46
7919
69
19
288
26430
15
-9678
351
-129158
53776
6646
48336
166303
59
133144
45343
343
175863
157528
41278
178
21658
194
90
163869
770
17639
-8899
-86276
1243
135725
-49699
16544
13578
33560
27393
25169
46164
206
79
1220
-126096
12408
16724
-63489
294...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%