QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#670522#5020. 举办乘凉州喵,举办乘凉州谢谢喵byron100000 0ms0kbC++149.5kb2024-10-23 22:02:522024-10-23 22:02:52

Judging History

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

  • [2024-10-23 22:02:52]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-10-23 22:02:52]
  • 提交

answer

#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define _UN using namespace
using namespace std;
struct IO{
    char in_buf[20*1048576],out_buf[20*1048576];
    int in_ptr,out_ptr;
    void init(){ fread(in_buf,1,sizeof(in_buf),stdin); }
    int read_int(){
        while(in_buf[in_ptr]<'0'||in_buf[in_ptr]>'9') in_ptr++;
        int ret=0;
        while(in_buf[in_ptr]>='0'&&in_buf[in_ptr]<='9') ret=ret*10+in_buf[in_ptr]-'0',in_ptr++;
        return ret;
    }
    void write_int(int x){
        char s[20]; int i=0;
        if(!x) i=1,s[0]='0';
        else{
            while(x) s[i++]=(x%10)+'0',x/=10;
            reverse(s,s+i);
        }
        copy_n(s,i,out_buf+out_ptr),out_ptr+=i;
    }
    void new_line(){ out_buf[out_ptr++]='\n'; }
    void done(){ fwrite(out_buf,1,out_ptr,stdout); }
} io;
const int MAXN=2e5+10,INF=1e9+10;
int n,qn; vector<int> G[MAXN];
int ans[MAXN];
int siz[MAXN],son[MAXN],dep[MAXN],fa[MAXN],top[MAXN],dfn[MAXN],dfnc;
namespace S0{
void dfs1(int u,int fa_){
    fa[u]=fa_,siz[u]=1,dep[u]=dep[fa_]+1;
    for(int v:G[u]){
        if(v==fa_) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int top_){
    dfn[u]=++dfnc,top[u]=top_;
    if(son[u]) dfs2(son[u],top_);
    for(int v:G[u]){
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
        else v=fa[top[v]];
    }
    return dep[u]<dep[v]?u:v;
}
int find_(int t,int u){
    assert(u!=t);
    int lst=-1;
    while(top[u]!=top[t]) lst=top[u],u=fa[top[u]];
    return t==u?lst:son[t];
}
} using S0::lca; using S0::find_;
struct Qt1{ int d,id; }; vector<Qt1> Q1[MAXN];
struct Qt2{ int d,id,op; }; vector<Qt2> Q2[MAXN]; // Query F
struct Qt3{ int d,id,op; }; vector<Qt3> Q3[MAXN]; // Query G
void add_qry(int u,int v,int d,int id){
    Q3[fa[u]].push_back({d,id,-1}),Q3[v].push_back({d,id,1});
    int lst=0;
    while(true){
        if(son[v]) Q2[son[v]].push_back({d-1,id,1});
        if(lst) Q2[lst].push_back({d-1,id,-1});
        if(top[u]==top[v]) break;
        lst=top[v],v=fa[top[v]];
    }
}
namespace S1{
struct BIT{
    int A[MAXN];
    vector<int> mdf;
    void upd(int i,int x){
        mdf.push_back(i);
        for(i++; i<=n+1; i+=i&-i) A[i]+=x;
    }
    int qry(int i){
        int ret=0;
        for(i++; i; i-=i&-i) ret+=A[i];
        return ret;
    }
    void reset(){
        for(int i0:mdf){
            for(int i=i0+1; i<=n+1; i+=i&-i) A[i]=0;
        }
        mdf.clear();
    }
} bit;
int siz[MAXN],dep[MAXN],bel[MAXN]; bool vis[MAXN];
void dfs2(int u,int fa,int totsz,pair<int,int>& rt){ // find root
    siz[u]=1;
    int mxsz=0;
    for(int v:G[u]){
        if(v==fa||vis[v]) continue;
        dfs2(v,u,totsz,rt);
        siz[u]+=siz[v];
        mxsz=max(mxsz,siz[v]);
    }
    mxsz=max(mxsz,totsz-siz[u]);
    rt=min(rt,pair<int,int>{mxsz,u});
}
int mxd;
void dfs1(int u,int fa){
    siz[u]=1,mxd=max(mxd,dep[u]);
    for(int v:G[u]){
        if(v!=fa&&!vis[v]) dep[v]=dep[u]+1,dfs1(v,u),siz[u]+=siz[v];
    }
}
int tot=0,sum[MAXN];
void dfs3(int u,int fa){
//  bit.upd(dep[u],1);
    tot++,sum[dep[u]]+=siz[u];
    for(int v:G[u]){
        if(v==fa||vis[v]) continue;
        dfs3(v,u);
    }
}
void dfs4(int u,int fa,int op){
    for(auto q:Q1[u]){
        if(q.d>=dep[u]){
//          ans[q.id]+=op*bit.qry(q.d-dep[u]);
            ans[q.id]+=op*(tot-sum[q.d-dep[u]+1]);
        }
    }
    for(int v:G[u]){
        if(v==fa||vis[v]) continue;
        dfs4(v,u,op);
    }
}
vector<int> vec[MAXN];
void dfs5(int u,int fa,vector<int>& vc){
    vc.push_back(u);
    for(int v:G[u]){
        if(v==fa||vis[v]) continue;
        dfs5(v,u,vc);
    }
}
void solve(int r){
    vis[r]=1,dep[r]=0;
    mxd=0;
    dfs1(r,0);
    dfs3(r,0),dfs4(r,0,1);
//  for(int v:G[r]){
//      if(!vis[v]) continue;
//      vec[v].reserve(siz[v]);
//      dfs5(v,r,vec[v]);
//      for(int w:vec[v]) bit.upd(dep[w],1);
//  }
//  bit.upd(0,1);
//  for(auto q:Q1[r]){
//      if(q.d>=dep[r]) ans[q.id]+=bit.qry(q.d-dep[r]);
//  }
//  for(int v:G[r]){
//      if(!vis[v]) continue;
//      for(int w:vec[v]){
//          for(auto q:Q1[w]){
//              if(q.d>=dep[w]) ans[q.id]+=bit.qry(q.d-dep[w]);
//          }
//      }
//  }
//  bit.reset();
    fill_n(sum,mxd+1,0),tot=0;
    for(int v:G[r]){
        if(vis[v]) continue;
        dfs3(v,r),dfs4(v,r,-1);
//      for(int w:vec[v]) bit.upd(dep[w],1);
//      for(int w:vec[v]){
//          for(auto q:Q1[w]){
//              if(q.d>=dep[w]) ans[q.id]-=bit.qry(q.d-dep[w]);
//          }
//      }
//      vec[v].clear();
//      bit.reset();
        fill_n(sum,mxd+1,0),tot=0;
    }
    for(int v:G[r]){
        if(vis[v]) continue;
        pair<int,int> rt {INF,0};
        dfs2(v,0,siz[v],rt);
        solve(rt.second);
    }
}
void main(){
    pair<int,int> rt {INF,0};
    dfs2(1,0,n,rt);
    solve(rt.second);
}
}
namespace S2{
struct SGT{
#define ls (T[u].ls_)
#define rs (T[u].rs_)
#define mid ((l+r)/2)
    struct{ int ls_,rs_,cnt; } T[MAXN*20]; int nnd;
    void ins(int& u,int l,int r,int i){
        if(!u) u=++nnd;
        T[u].cnt++;
        if(l==r) return;
        i<=mid ? ins(ls,l,mid,i) : ins(rs,mid+1,r,i);
    }
    void pushup(int u){ T[u].cnt=T[ls].cnt+T[rs].cnt; }
    int qry(int u,int l,int r,int qr){
        if(r<=qr) return T[u].cnt;
        return qry(ls,l,mid,qr)+(mid<qr?qry(rs,mid+1,r,qr):0);
    }
    int merge(int u,int v,int l,int r){
        if(!u||!v) return u|v;
        if(l==r){ T[u].cnt+=T[v].cnt; return u; }
        ls=merge(ls,T[v].ls_,l,mid),rs=merge(rs,T[v].rs_,mid+1,r);
        pushup(u);
        return u;
    }
#undef ls
#undef rs
#undef mid
} sgt;
int rt[MAXN];
int son[MAXN],mxd[MAXN];
void dfs2(int u){
    mxd[u]=dep[u];
    for(int v:G[u]){
        if(v==fa[u]) continue;
        dfs2(v);
        mxd[u]=max(mxd[u],mxd[v]);
        if(mxd[v]>mxd[son[u]]) son[u]=v;
    }
}
struct X {
    vector<int> A,S;
    int& atA(int i){ return A[int(A.size())-i-1]; }
    int atS1(int i) const { return i<int(S.size())?S[int(S.size())-i-1]:0; }
    int& atS(int i){ return S[int(S.size())-i-1]; }
};
X dfs(int u){
//  sgt.ins(rt[u],1,n,dep[u]);
//  for(int v:G[u]){
//      if(v!=fa[u]) dfs(v),rt[u]=sgt.merge(rt[u],rt[v],1,n);
//  }
//  for(auto q:Q2[u]) ans[q.id]+=q.op*sgt.qry(rt[u],1,n,q.d+dep[u]);
    X ret;
    if(son[u]) ret=dfs(son[u]);
    ret.A.push_back(1),ret.S.push_back(0);
    int mx=0;
    for(int v:G[u]){
        if(v!=fa[u]&&v!=son[u]){
            auto x=dfs(v);
            mx=max(mx,int(x.A.size()));
            RNG(i,0,int(x.A.size())-1) ret.atA(i+1)+=x.atA(i);
        }
    }
    IRNG(i,mx,0){
        ret.atS(i)=ret.atS1(i+1)+ret.atA(i);
    }
    for(auto q:Q2[u]){
        ans[q.id]+=q.op*(ret.atS(0)-ret.atS1(q.d+1));
    }
    return ret;
}
void main(){
    dfs2(1);
    dfs(1);
}
}
namespace S3{
int tot=0,sum[MAXN];
void dfs2(int u,int d,int op,vector<int>& vec,int& cnt){
    tot+=op,sum[dep[u]-d]+=op*siz[u];
    cnt++;
    if(int(vec.size())<=dep[u]-d) vec.push_back(0);
    vec[dep[u]-d]+=siz[u];
    for(int v:G[u]){
        if(v!=fa[u]) dfs2(v,d,op,vec,cnt);
    }
}
void dfs1(int u){
    tot++,sum[0]+=siz[u];
    vector<int> vec {0}; int cnt=0;
    for(int v:G[u]){
        if(v!=fa[u]&&v!=son[u]) dfs2(v,dep[u],1,vec,cnt);
    }
    for(auto q:Q3[u]) ans[q.id]+=q.op*(tot-sum[q.d+1]);
    for(int v:G[u]){
        if(v==fa[u]) continue;
        dfs1(v);
    }
    tot--,sum[0]-=siz[u];
    tot-=cnt;
    RNG(i,0,int(vec.size())-1) sum[i]-=vec[i];
}
void main(){ dfs1(1); }
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
    freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
    freopen("future.in","r",stdin);
    freopen("future.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    io.init();
//  cin>>n;
    n=io.read_int();
//  RNG(_,1,n-1,u,v) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
    RNG(_,1,n-1,u,v) u=io.read_int(),v=io.read_int(),G[u].push_back(v),G[v].push_back(u);
    S0::dfs1(1,0),S0::dfs2(1,1);
//  cin>>qn;
    qn=io.read_int();
    RNG(i,1,qn){
        int u,v,d;
        // cin>>u>>v>>d;
        u=io.read_int(),v=io.read_int(),d=io.read_int();
        if(d==0){
            int t=lca(u,v);
            ans[i]=dep[u]+dep[v]-2*dep[t]+1;
            continue;
        }
        if(dfn[u]>dfn[v]) swap(u,v);
        if(u==v) Q1[u].push_back({d,i});
        else if(dfn[v]<dfn[u]+siz[u]){
            int v1=find_(u,v);
            Q1[u].push_back({d,i}),Q2[v1].push_back({d-1,i,-1});
            add_qry(v1,v,d,i);
        }else{
            int t=lca(u,v),u1=find_(t,u),v1=find_(t,v);
            Q1[t].push_back({d,i}),Q2[u1].push_back({d-1,i,-1}),Q2[v1].push_back({d-1,i,-1});
            add_qry(u1,u,d,i),add_qry(v1,v,d,i);
        }
    }
    S1::main();
    S2::main();
    S3::main();
//  RNG(i,1,qn) cout<<ans[i]<<"\n";
    RNG(i,1,qn) io.write_int(ans[i]),io.new_line();
    io.done();
//  cerr<<S1::_c1<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

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:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #9:

score: 0
Dangerous Syscalls

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:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Dangerous Syscalls

Test #25:

score: 0
Dangerous Syscalls

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:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%