Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
35853 LYLAKIOI 【S】T4 C++ 通过 100 535 MS 38232 KB 2800 2025-01-05 19:52:41

Tests(20/20):


#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair using namespace std; typedef long long ll; const int maxn=1e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,dep[maxn],mxd[maxn],fa[maxn][20],dfn[maxn],siz[maxn],ct; vector<int>E[maxn]; struct SegTree { int mn[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void bd(int l,int r,int p){ mn[p]=1e9; if(l==r)return; int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p)); }stack<pi>S; void modify(int l,int s,int t,int p,int x){ S.push(m_p(p,mn[p]));mn[p]=min(mn[p],x); if(s==t)return; int mid=s+t>>1; if(l<=mid)modify(l,s,mid,ls(p),x);else modify(l,mid+1,t,rs(p),x); }int qry(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return mn[p]; int mid=s+t>>1,res=1e9; if(l<=mid)res=min(res,qry(l,r,s,mid,ls(p)));if(r>mid)res=min(res,qry(l,r,mid+1,t,rs(p))); return res; }void rvk(){ while(!S.empty()){ int u=S.top().p1,c=S.top().p2;S.pop(); mn[u]=c; } } }T; vector<int>G[maxn]; int res[maxn]; void dfs(int u){ dep[u]=dep[fa[u][0]]+1,mxd[u]=1e9; dfn[u]=++ct,siz[u]=1; for(int x:E[u])if(x!=fa[u][0]){ fa[x][0]=u,dfs(x);mxd[u]=min(mxd[u],mxd[x]);siz[u]+=siz[x]; } //cout<<u<<" "<<mxd[u]-dep[u]<<endl; if(mxd[u]==(int)1e9)mxd[u]=dep[u]; G[mxd[u]-dep[u]].p_b(u); } int kfa(int u,int k){ down(i,19,0)if((k>>i)&1)u=fa[u][i]; return u; } int get_ans(int k){ priority_queue<pi>q; for(int x:G[k])q.push(m_p(dep[x],x)); int res=G[0].size(); while(!q.empty()){ int u=q.top().p2;q.pop(); if(T.qry(dfn[u],dfn[u]+siz[u]-1,1,n,1)-dep[u]<k)continue; res++;T.modify(dfn[u],1,n,1,dep[u]); if(dep[u]>k)q.push(m_p(dep[u]-k,kfa(u,k))); }T.rvk();return res; } void slv(){ n=read();up(i,1,n-1){ int x=read(),y=read(); E[x].p_b(y),E[y].p_b(x); }dfs(1);up(i,1,19)up(j,1,n)fa[j][i]=fa[fa[j][i-1]][i-1]; T.bd(1,n,1); up(i,1,n)if(dep[i]==mxd[i])T.modify(dfn[i],1,n,1,dep[i]); while(!T.S.empty())T.S.pop(); up(i,1,n)res[i]=get_ans(i); int q=read(); while(q--)printf("%d\n",res[min(n,(int)read())]); } int main(){ //freopen("tree.in","r",stdin); //freopen("tree.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }


测评信息: