QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345180#5020. 举办乘凉州喵,举办乘凉州谢谢喵ANIG0 63ms51356kbC++145.9kb2024-03-06 14:16:132024-03-06 14:16:13

Judging History

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

  • [2024-03-06 14:16:13]
  • 评测
  • 测评结果:0
  • 用时:63ms
  • 内存:51356kb
  • [2024-03-06 14:16:13]
  • 提交

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=0;i<p[x].size();i++){
        int c=p[x][i];
        if(mk[c]||c==zs[x])continue;
        dfs7(f[x],c,x);
    }
    for(int i=1;i<f[x].size();i++)f[x][i]+=f[x][i-1];
    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-dp[x]-1,0ll),k-1);
        gs[dfn[d[x]]-1].push_back({k,-op,bh});
        gs[dfn[x]].push_back({k,op,bh});
        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<=n;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: 63ms
memory: 51356kb

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 1 1 7 462
1 1 -2 7 462
1 2 1 5 311
1 2 -2 5 311
1 3 1 15 7
1 3 -2 15 7
1 4 1 2 39
1 4 -2 2 39
1 6 1 8 429
1 6 -2 8 429
1 7 1 8 429
1 7 -2 8 429
1 8 1 5 311
1 8 -2 5 311
1 9 1 14 16
1 9 -2 14 16
1 10 1 6 409
1 10 1 6 409
1 10 -2 6 409
1 11 1 2 39
1 11 -2 2 39
1 12 1 3 75
1 12 1 3 75
1 12 -2 3 75
1 ...

result:

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

Subtask #2:

score: 0
Time Limit Exceeded

Test #9:

score: 0
Time Limit Exceeded

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 1 1 10 12212
1 1 1 10 12212
1 1 -2 10 12212
1 3 1 18 906
1 3 1 18 906
1 3 -2 18 906
1 4 1 24 2
1 4 1 24 2
1 4 -2 24 2
1 5 1 23 9
1 5 1 23 9
1 5 -2 23 9
1 6 1 9 11262
1 6 1 9 11262
1 6 -2 9 11262
1 7 1 18 906
1 7 1 18 906
1 7 -2 18 906
1 8 1 30 0
1 8 1 30 0
1 8 -2 30 0
1 12 1 28 0
1 12 1 28 0
1 12 ...

result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #25:

score: 0
Time Limit Exceeded

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 1 1 1 10
1 1 -2 1 10
1 3 1 16 5450
1 3 1 16 5450
1 3 -2 16 5450
1 4 1 4 764
1 4 -2 4 764
1 5 1 10 15502
1 5 -2 10 15502
1 7 1 5 1917
1 7 1 5 1917
1 7 -2 5 1917
1 8 1 10 15502
1 8 -2 10 15502
1 10 1 5 1917
1 10 -2 5 1917
1 11 1 1 10
1 11 -2 1 10
1 13 1 2 50
1 13 -2 2 50
1 14 1 20 475
1 14 -2 20 475...

result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%