QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#670522 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | byron10000 | 0 | 0ms | 0kb | C++14 | 9.5kb | 2024-10-23 22:02:52 | 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%