QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185039 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | zyz07 | 0 | 0ms | 0kb | C++17 | 4.6kb | 2023-09-21 16:15:24 | 2023-09-21 16:15:25 |
answer
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=2e5+5;
int n,q,vis[N],siz[N],mxsiz[N];
vector<int> e[N];
struct Query{
int u,v,k;
}qry[N];
int ans[N];
void get_root(int u,int fa,int tot,int& rt){
siz[u]=1;
mxsiz[u]=0;
for(int v:e[u]){
if(v!=fa&&!vis[v]){
get_root(v,u,tot,rt);
siz[u]+=siz[v];
mxsiz[u]=max(mxsiz[u],siz[v]);
}
}
mxsiz[u]=max(mxsiz[u],tot-siz[u]);
if(!rt||mxsiz[u]<mxsiz[rt]){
rt=u;
}
}
int bel[N];
vector<int> deps[N],nxt_qs[N];
void fill(int u,int fa,int d,int rt){
if(int(deps[rt].size())<=d){
deps[rt].resize(d+1);
}
++deps[rt][d];
bel[u]=rt;
for(int v:e[u]){
if(v!=fa&&!vis[v]){
fill(v,u,d+1,rt);
}
}
}
namespace Solver{
int fa[N],dep[N],son[N],hson[N],siz[N],mxdep[N];
vector<int> poi;
struct Query{
int id,v,k;
}qry[N*2];
void dfs(int u){
poi.push_back(u);
dep[u]=dep[fa[u]]+1;
siz[u]=1;
for(int v:e[u]){
if(v!=fa[u]&&!vis[v]){
fa[v]=u;
dfs(v);
mxdep[u]=max(mxdep[u],mxdep[v]+1);
siz[u]+=siz[v];
if(mxdep[v]>=mxdep[son[u]]) son[u]=v;
if(siz[v]>siz[hson[u]]) hson[u]=v;
}
}
}
int top[N],dfn[N],dfx,rk[N];
void dfs2(int u,int tp){
top[u]=tp;
rk[dfn[u]=++dfx]=u;
if(hson[u]) dfs2(hson[u],tp);
for(int v:e[u]){
if(v!=fa[u]&&v!=hson[u]&&!vis[v]){
dfs2(v,v);
}
}
}
vector<tuple<int,int,int>> qs[N];
vector<pair<int,int>> hldqs[N];
int *f[N],buff[N*2],*cur;
void dfs3(int u){
if(son[u]) f[son[u]]=f[u]+1,dfs3(son[u]);
for(int v:e[u]){
if(v!=fa[u]&&v!=son[u]&&!vis[v]){
f[v]=cur,cur+=mxdep[v]+1;
dfs3(v);
For(i,0,mxdep[v]) f[u][i+1]+=f[v][i];
}
}
if(son[u]) f[u][0]=f[u][1]+1;
else f[u][0]=1;
for(auto [id,k,w]:qs[u]){
ans[qry[id].id]+=w*(f[u][0]-(k<mxdep[u]?f[u][k+1]:0));
}
}
void solve(int q,int rt){
dfs(rt);
dfs2(rt,rt);
For(i,1,q){
ans[qry[i].id]+=dep[qry[i].v]-1;
if(!qry[i].k){
++ans[qry[i].id];
continue;
}
qs[qry[i].v].emplace_back(i,qry[i].k,1);
for(int u=qry[i].v;u!=rt;u=top[u]){
hldqs[fa[u]].emplace_back(i,1);
qs[u].emplace_back(i,qry[i].k-1,-1);
qs[hson[fa[u]]].emplace_back(i,qry[i].k-1,1);
u=fa[u];
}
}
vector<int> val;
for(int i:poi){
int cnt=0;
for(int v:e[i]){
if(v!=fa[i]&&!vis[v]){
++cnt;
}
}
if(!cnt){
vector<int> pth;
for(int u=i;u!=top[u];u=fa[u]){
pth.push_back(u);
}
pth.push_back(top[i]);
reverse(range(pth));
val.clear();
int ssiz=0;
for(int u:pth){
for(int v:e[u]){
if(v!=fa[u]&&v!=hson[u]&&!vis[v]){
val.resize(max<int>(val.size(),mxdep[v]+1));
For(j,dfn[v],dfn[v]+siz[v]-1){
int x=rk[j];
++ssiz;
val[dep[x]-dep[v]]+=siz[x];
}
}
}
for(auto [id,w]:hldqs[u]){
int k=qry[id].k;
ans[qry[id].id]+=w*(ssiz-(k<int(val.size())?val[k]:0));
}
}
}
}
f[rt]=cur=buff;
cur+=mxdep[rt]+1;
dfs3(rt);
For(i,0,2*int(poi.size())){
buff[i]=0;
}
for(int u:poi){
fa[u]=son[u]=hson[u]=mxdep[u]=0;
qs[u].clear();
hldqs[u].clear();
}
poi.clear();
dfx=0;
}
}
void solve(int u,const vector<int>& qs){
int rt=0;
get_root(u,0,siz[u],rt);
u=rt;
vis[u]=1;
bel[u]=u;
deps[u]={1};
vector<int> vec;
for(int v:e[u]){
if(!vis[v]){
fill(v,u,1,v);
if(vec.size()<deps[v].size()){
vec.resize(deps[v].size());
}
For(i,1,int(deps[v].size())-1){
deps[v][i]+=deps[v][i-1];
}
For(i,0,int(deps[v].size())-1){
vec[i]+=deps[v][i];
}
}
}
For(i,0,int(vec.size())-1){
++vec[i];
}
int qcnt=0;
for(int i:qs){
auto [u,v,k]=qry[i];
if(bel[u]!=bel[v]||(bel[u]==rt&&bel[v]==rt)){
ans[i]-=vec[min(k,int(vec.size())-1)];
Solver::qry[++qcnt]={i,u,k};
Solver::qry[++qcnt]={i,v,k};
}else{
nxt_qs[bel[u]].push_back(i);
}
}
Solver::solve(qcnt,u);
deps[u].clear();
for(int v:e[u]){
if(!vis[v]){
deps[v].clear();
}
}
for(int v:e[u]){
if(!vis[v]){
solve(v,nxt_qs[v]);
}
}
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
For(i,1,n-1){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
siz[1]=n;
vector<int> qs;
cin>>q;
For(i,1,q){
cin>>qry[i].u>>qry[i].v>>qry[i].k;
qs.push_back(i);
}
solve(1,qs);
For(i,1,q) cout<<ans[i]<<'\n';
return 0;
}
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
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
Runtime Error
Test #9:
score: 0
Runtime Error
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
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%