Skip to content

倍增

普通倍增

P7167

这道题非常坑 要注意倍增到最后可能有剩余，这时候要特判一下，如果有剩余则应该流向下一个盘子(喷泉)中

树上倍增

经典应用：倍增\(lca\)，维护树上一段区间(链)信息，寻找树上节点。

P1084

假设当前有一个时间限制，可以发现对于每个军队，一定时越靠近根节点越优。并且一个时间限制如果能满足，那么比他大的时间限制就都能满足。

有这两个单调性，就可以树上倍增+二分。每次二分一个时间限制，并将所有军队用树上倍增的方式推到它能到的深度最小的节点。并找出所有能自由活动的军队去满足那些没有军队驻守的根的子节点。

按照剩余时间的排序顺序贪心的去一一解决就行了。

最后返回是否满足这个时间限制。

update.2022.4.5

昨天写了这个题，发现比我想象地恶心得多啊，再来吐槽一下。

  1. 预处理

首先，树上倍增求出\(dis[u][j]\),表示一段距离。

  1. 上移军队

然后，对于每个军队，我们将他向上推到深度最小(不是根)的地方。如果该节点不在根节点下面，或它剩余时间无法到达根，就在当前节点驻扎(\(vis[u]=1\))

否则将军队加入一个二元组\(h\)中备用，二元组第一维是它到达根节点时的剩余时间，第二维时它来自根的哪个子节点。

  1. 统计答案

先对于根的子节点做深搜，得出那些节点不用军队驻扎，剩余那些节点需要军队驻扎。

之后，对于二元组按第一维从小到大排序。如果满足：!vis[h[i].n] && h[i].d<dis[h[i].n][0],就将军队驻扎在\(h[i].n\).（这个贪心后面会说明）

最后，将那些仍然需要驻扎的子节点拿出来，按照到根的距离从小到大排序，与空闲军队匹配(双指针)。这里也用到了很显然的贪心。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define int long long 
using namespace std;
const int N=1e5+10,K=21,INF=1e15;
struct edge{
    int v,w,nxt;
}e[N<<1];
struct node{
    int d,n;
    node(int dd=0,int nn=0){
        d=dd,n=nn;
    }
}h[N],s[N];
int n,m,u,v,w,cnt;
int head[N],fa[N][K],dis[N][K],vis[N],t[N],a[N];
void add(int u,int v,int w){
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}
void dfs(int u,int p){
    for(int i=1;i<K;++i) fa[u][i]=fa[fa[u][i-1]][i-1],dis[u][i]=dis[u][i-1]+dis[fa[u][i-1]][i-1];
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v,w=e[i].w;
        if(v==p) continue;
        fa[v][0]=u,dis[v][0]=w;
        dfs(v,u);
    }
}
bool _dfs(int u,int p){
    if(vis[u]) return 1;
    int o=0;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(v==p) continue;
        if(!_dfs(v,u)) return 0;
        o=1;
    }
    if(!o) return 0;
    return 1;
}
bool cmp(node a,node b){
    if(a.d==b.d) return a.n<b.n;
    return a.d<b.d;
}
bool Cmp(int a,int b){
    return a<b;
}
bool _cmp(int a,int b){
    return dis[a][0]<dis[b][0];
}
bool check(int x){
    memset(vis,0,sizeof vis);
    memset(h,0,sizeof h);
    memset(s,0,sizeof s);
    memset(t,0,sizeof t);
    int tot=0,top=0,cur=0,atot=0,btot=0;
    for(int i=1;i<=m;++i){
        int u=a[i],tmp=0;
        for(int j=K-1;j>=0;--j) if(fa[u][j]>1 && tmp+dis[u][j]<=x) tmp+=dis[u][j],u=fa[u][j];
        if(fa[u][0]==1 && tmp+dis[u][0]<=x){
            h[++tot]=node(x-tmp-dis[u][0],u);
        }else vis[u]=1;
    }
    for(int i=head[1];~i;i=e[i].nxt){
        int v=e[i].v;
        vis[v]=_dfs(v,1);
    }
    sort(h+1,h+tot+1,cmp);
    for(int i=1;i<=tot;++i){
        if(!vis[h[i].n] && h[i].d<dis[h[i].n][0]) vis[h[i].n]=1;
        else s[++top]=h[i];
    }
    for(int i=head[1];~i;i=e[i].nxt){
        int v=e[i].v;
        if(!vis[v]) t[++cur]=v;
    }
    sort(s+1,s+top+1,cmp);
    sort(t+1,t+cur+1,_cmp);
    int l=1;
    for(int i=1;i<=cur;++i){
        while(l<=top && s[l].d<dis[t[i]][0]) ++l;
        if(l<=top) vis[t[i]]=1,++l;
        else return 0;
    }
    return 1;
}
signed main(){
    //freopen("P1084_2.in","r",stdin);
    memset(head,-1,sizeof head),cnt=-1;
    scanf("%lld",&n);
    for(int i=1;i<n;++i) scanf("%lld%lld%lld",&u,&v,&w),add(u,v,w),add(v,u,w);
    dfs(1,0);
    scanf("%lld",&m);
    for(int i=1;i<=m;++i) scanf("%lld",&a[i]);
    int l=0,r=INF,ans=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}
/*
10 
2 1 3
2 3 4
1 4 7
5 1 9
6 1 2
4 7 9
7 8 8
9 8 8
1 10 2
5
2 8 5 4 2 
*/

下面说说坑点：

  1. 树上倍增

树上倍增一定要在递归到下一层前就递推出这一层得\(dis[u][j],fa[u][j]\),不然，相当于递归到底，前面的\(dis[u][j]\)还都是空的，就会出错了

  1. 贪心部分

先考虑一个反例：

hack_0

这里就不用二元组表示了，直接展示原始状态，红色表示剩余时间，蓝色表示边权。

可以发现，如果让\(9\)驻扎在\(2\)号节点，最终就只能驻扎\(3\)个，而正确答案为\(4\).

然后尝试~~证明~~说明一下原理。

因为军队\(i\)满足h[i].d<dis[h[i].n][0],那这个军队无法再回到它所属的子节点，所以该子节点一定由另一个剩余时间大于它的军队\(j\)控制。而显然\(j\)可以到达的节点数多于\(i\)，所以直接让\(i\)管控这个子节点更优。

而如果\(i\)不满足，说明它能回去，那就将他加入最后的数组与后面的军队一起考虑。虽然让他折返会浪费时间，但是结果不会更差，这样简化了决策复杂度。

P3233

~~关于虚树模板写假了调了一上午这件事~~

这道题及其~~恶心~~复杂,需要\(6\)次\(dfs\)。

  1. 预处理\(lca,dep,size\)

倍增处理\(fa\)，因为后面除了求\(lca\)还会用到。

  1. 求出虚树中每个虚树节点子树中距离此节点最近的"关键节点"

所有关键节点都在虚树上，所以第一遍从下而上\(dfs\)，可以求出每个节点在它子树中距离它最近的关键节点(可以是自己)。

  1. 求出虚树中距离每个虚树节点最近的"关键节点"

第二遍从上而下求出子树外贡献。

注意，我们维护的是一个二元组\(g[u]\)，第一关键字为距离，第二关键字为编号。

  1. 求出虚树上每个节点距离最近的点编号，以及节点上的贡献。

最近节点就是\(num[u]=g[u].second\),而节点上的贡献是指：对于虚树节点\(u\)，其所有没有关键点的子树，都将归\(num[u]\)管理。

所以，我们遍历虚树时，可以用\(u\)所在的子树总结点数减去有关键点的子树大小。

有关键点的子树大小需要在原树上倍增求出对于\(v\)所在子树的根\(up[v]\)，这时\(up[v]\)在\(u\)下面，减掉\(sz[up[v]]\)即可。

  1. 求出虚树上每条边的贡献

对于每条边两端点\(u,v\)，有两种情况：

一是\(num[u]=num[v]\),这种情况这条边上所有节点都归\(num[u]\)管即可。

二是\(num[u]\not =num[v]\),这种情况先求出中间点的深度，再从\(v\)倍增找出中间点标号即可。

具体地，从\(num[u]\)到\(num[v]\)的链长度\(L\)=\(dep[num[v]]-dep[u]+g[u].first\).

那么中间点的深度=\(\frac{dep[num[v]]-L} 2\).

  1. 清空虚树及点标记

需要清空\(vis[i],ans[i],up[i],num[i]\).

至此，这道题才算做完。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
using namespace std;
typedef pair<int,int> PI;
const int N=3e5+10,K=20,INF=0x3f3f3f3f;
int fa[N][K],dep[N],head[2][N],vis[N],a[N],b[N],sz[N],stk[N],ans[N],id[N],num[N],up[N];
int n,q,u,v,cnt[2],tmp,m,top,tot,rt;
PI g[N];
struct edge {
    int v,nxt;
} e[2][N<<1];
void add(int u,int v,int i) {
    e[i][++cnt[i]].v=v,e[i][cnt[i]].nxt=head[i][u],head[i][u]=cnt[i];
}
bool cmp(int a,int b) {
    return id[a]<id[b];
}
int read1(){
    int x=0;char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
void write1(int x){
    if(x>9) write1(x/10);
    putchar(x%10+'0');  
}
void dfs0(int u,int p) {
    id[u]=++tot;fa[u][0]=p;sz[u]=1;
    for(int i=1; i<K; ++i) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[0][u]; ~i; i=e[0][i].nxt) {
        int v=e[0][i].v;
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dfs0(v,u);
        sz[u]+=sz[v];
    }
}
void dfs1(int u,int p) {
    if(vis[u]) g[u]=make_pair(0,u);
    else g[u]=make_pair(INF,0);
    for(int i=head[1][u]; ~i; i=e[1][i].nxt) {
        int v=e[1][i].v;
        if(v==p) continue;
        dfs1(v,u);
        g[u]=min(g[u],make_pair(g[v].first+dep[v]-dep[u],g[v].second));
    }
}
void dfs2(int u,int p,int d,int x) {
    PI tmp=make_pair(d,x);
    if(tmp<g[u]) g[u]=tmp;
    else d=g[u].first,x=g[u].second;
    for(int i=head[1][u]; ~i; i=e[1][i].nxt) {
        int v=e[1][i].v;
        if(v==p) continue;
        dfs2(v,u,d+dep[v]-dep[u],x);
    }
}
void dfs3(int u,int p) {
    num[u]=g[u].second;
    ans[num[u]]+=sz[u];
    for(int i=head[1][u]; ~i; i=e[1][i].nxt) {
        int v=e[1][i].v;
        if(v==p) continue;
        int k=v;
        for(int j=K-1;j>=0;--j) if(fa[k][j] && dep[fa[k][j]]>dep[u]) k=fa[k][j];
        ans[num[u]]-=sz[up[v]=k];
        dfs3(v,u);
    }
}
void dfs4(int u,int p){
    for(int i=head[1][u]; ~i; i=e[1][i].nxt) {
        int v=e[1][i].v;
        if(v==p) continue;
        if(num[v]==num[u]) ans[num[u]]+=(sz[up[v]]-sz[v]);
        else{
            int dis=dep[num[v]]+dep[u]-g[u].first;
            dis=dis&1?dis+1>>1:(num[v]<num[u]?dis>>1:(dis>>1)+1);
            int k=v;
            for(int j=K-1;j>=0;--j) if(fa[k][j] && dep[fa[k][j]]>=dis) k=fa[k][j];
            ans[num[u]]+=sz[up[v]]-sz[k];
            ans[num[v]]+=sz[k]-sz[v];
        }
        dfs4(v,u);
    }
}
void dfs5(int u,int p){//clear
    up[u]=num[u]=0;
    for(int i=head[1][u]; ~i; i=e[1][i].nxt) {
        int v=e[1][i].v;
        if(v==p) continue;
        dfs5(v,u);
    }
    head[1][u]=-1;
}
int getlca(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    int k=dep[u]-dep[v];
    for(int i=K-1; i>=0; --i) if(k&(1<<i)) u=fa[u][i];
    if(v==u) return u;
    for(int i=K-1; i>=0; --i) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
void insert(int u) {
    int lca=getlca(u,stk[top]);
    while(top>1 && id[stk[top-1]]>=id[lca]) add(stk[top],stk[top-1],1),add(stk[top-1],stk[top],1),--top;
    if(lca!=stk[top]) add(stk[top],lca,1),add(lca,stk[top],1),stk[top]=lca;
    stk[++top]=u;
}
void build() {
    cnt[1]=-1;
    sort(a+1,a+m+1,cmp);
    stk[top=1]=a[1];
    for(int i=2; i<=m; ++i) insert(a[i]);
    while(top>1) add(stk[top],stk[top-1],1),add(stk[top-1],stk[top],1),--top;
    rt=stk[1];
}
int main() {
    memset(head,-1,sizeof head);
    cnt[0]=-1;
    scanf("%d",&n);
    for(int i=1; i<n; ++i) scanf("%d%d",&u,&v),add(u,v,0),add(v,u,0);
    dfs0(1,0);
    scanf("%d",&q);
    for(int i=1; i<=q; ++i) {
        scanf("%d",&m);
        for(int j=1; j<=m; ++j) scanf("%d",&a[j]),b[j]=a[j],vis[b[j]]=1;
        build();
        dfs1(rt,0);
        dfs2(rt,0,g[rt].first,g[rt].second);
        dfs3(rt,0);
        dfs4(rt,0);
        ans[num[rt]]+=sz[1]-sz[rt];
        for(int j=1; j<=m; ++j) printf("%d ",ans[b[j]]),ans[b[j]]=vis[b[j]]=0;printf("\n");
        dfs5(rt,0);
    }
    return 0;
}

P7518

~~做了整整两天才过的恶心题~~

~~100紫题祭！~~

~~思路很简单，代码100行，但细节真的多~~

首先可以将路径\(s\to t\)拆分为上行\(s\to lca\)和下行\(lca\to t\)

对于每个树上的节点，我们都可以通过倍增来求出\(f[u][j]\)，表示它经过原序列\(2^j\)个宝石后向上跳到了哪个节点。

每次二分找到上行路径中的第一个于原序列对应的节点(起点)，从它开始倍增，便可以解决上行的情况。下行也同理。

接下来就是一堆细节了。

  1. 求解\(f[u][j]\).

我们发现，只要有了\(f[u][0]\),剩余就可以递推解决。

而\(f[u][0]\)可以用\(c\)个栈\(h\)维护一下，即对于每个宝石开一个栈。

而因为我们要知道每个宝石下一个宝石的编号，所以可以提前求一个\(nxt[i]\)表示宝石\(i\)的下一个，也可以求出\(rk[i]\),表示宝石\(i\)的相对排名。

\(dfs\)每经过一个节点，就将这个节点的编号加入\(rk[a[u]]\)这个栈里。(栈的下标为宝石相对排名。)

每次对于节点\(u\)，访问\(h[rk[a[u]]+1]\)的栈顶(注意特判栈为空，不然会\(RE\))，就是深度最深的\(f[u][0]\)了。

  1. 二分起点

二分一定要利用单调性，然而只看宝石种类无法得出单调性。

所以我们要用到\(dfs\)序。

对于每个宝石\(i\)，求出它在那些\(dfs\)序对应的节点出现过，记为\(d[i]\)。\(dfs\)序从小到大。

那么，我么就可以根据\(dfs\)序的性质，用树剖将树分成几条重链。重链上\(dfs\)序连续，所以可以在\(d[i]\)中二分最后一个\(\leq\)树链下端点\(dfs\)序的\(dfs\)序值\(tmp\)。如果\(tmp\)在\(id[top[t]],id[t]\)之间，就说明找到了，否则继续向上找。

复杂度\(O(\log^2n)\),一共\(O(\log n)\)条链。

  1. 倍增

如果找到起点再进行倍增，不然倍增就没意义了。

  1. 下行

~~《下行也同理》，当时我是这么想的~~

首先，我们注意到一个事：倍增数组只能向上，不能向下，因为一个父亲对应多个儿子。

所以这里我们仍然要求一个向上的倍增数组\(g[u][j]\),只不过要求\(h[rk[a[u]-1]\),逆着向上即顺着向下。

求出这个后发现，我们需要知道最终答案才能从\(t\)开始二分起点+倍增，不然起点不确定，没法倍增。

还好这个答案具有单调性，即如果较大的答案已经满足，那么较小的答案一定满足。(相当于求出的序列和前面序列可以有重合，但不能有空隙。)

这样，我们就二分一个最终答案，然后从找到的起点向上倍增，注意要减掉所有贡献，之后判断一下两段是否有重叠即可。(这里的两段就是做多向前/向后倍增了多少个宝石。)

并且，这个二分要判断如果\(mid\)小于上行的答案，那么明显成立。

至此，我们解决了这道题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int N=2e5+10,M=5e4+10,K=23;
int b[N],a[N],head[N],sz[N],top[N],son[N],fa[N],dep[N],id[N],dfn[N],f[N][K],g[N][K],rk[N];
int n,m,c,q,cnt,tot,u,v,lca,num;
vector<int> d[N];
stack<int> h[N];
struct edge{
    int v,nxt;
}e[N<<1];
void add(int u,int v){
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}
int read1(){
    int x=0;char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
void write1(int x){
    if(x>9) write1(x/10);
    putchar(x%10+'0');
}
void dfs1(int u,int p){
    sz[u]=1;
    h[rk[a[u]]].push(u);
    f[u][0]=h[rk[a[u]]+1].empty()?0:h[rk[a[u]]+1].top(),g[u][0]=h[rk[a[u]]-1].empty()?0:h[rk[a[u]]-1].top();
    for(int i=1;i<K;++i) f[u][i]=f[f[u][i-1]][i-1],g[u][i]=g[g[u][i-1]][i-1];
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(v==p) continue;
        fa[v]=u,dep[v]=dep[u]+1;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]) son[u]=v;
    }
    h[rk[a[u]]].pop();
}
void dfs2(int u,int t){
    top[u]=t,id[u]=++tot,dfn[tot]=u;
    if(son[u]) dfs2(son[u],t);
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}
int getlca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(v,u);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
void Get(int &u,int &now,int x,int t){
    u=0,now=0;
    while(id[t]>=id[lca]){
        int idx=upper_bound(d[b[x]].begin(),d[b[x]].end(),id[t])-d[b[x]].begin()-1;
        if(idx>=0 && d[b[x]][idx]>=max(id[lca],id[top[t]])) {
            u=dfn[d[b[x]][idx]];now=x;
            break;
        }
        t=fa[top[t]];
    }
}
bool check(int ans,int x,int t){
    if(x<ans) return true;
    int u=0,now=0;
    Get(u,now,x,t);
    if(!now) return false;
    for(int j=K-1;j>=0;--j) if(g[u][j] && id[g[u][j]]>id[lca]) u=g[u][j],now-=(1<<j);
    return now<=ans;
}
void work(int s,int t){
    lca=getlca(s,t);int u=0,now=0;
    Get(u,now,1,s);
    if(now) for(int j=K-1;j>=0;--j) if(f[u][j] && id[f[u][j]]>=id[lca]) u=f[u][j],now+=(1<<j);
    int l=1,r=c,ans=0;
    while(l<=r){
        int mid=l+r>>1;
        if(check(now+1,mid,t)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    write1(ans),putchar('\n');
}
int main(){
    memset(head,-1,sizeof head),cnt=-1;
    n=read1(),m=read1(),c=read1();
    for(int i=1;i<=c;++i) b[i]=read1();
    for(int i=1;i<=n;++i) a[i]=read1();
    for(int i=1;i<=c;++i) rk[b[i]]=i;
    for(int i=1;i<n;++i) u=read1(),v=read1(),add(u,v),add(v,u);
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=tot;++i) d[a[dfn[i]]].push_back(i);
    q=read1();
    for(int i=1;i<=q;++i) u=read1(),v=read1(),work(u,v);
    return 0;
}

P2597

对于每个点会灭绝，当且仅当它的所有食物都灭绝了。也就是说，这些食物的共同lca一定灭绝。所以可以在拓扑排序过程中对于每个点维护一个\(dad\)数组，存所有食物的共同lca。求出数组后，将\(dad[i]\)与i连边，构成新的灭绝树。答案为\(sz[u]-1\)。在每次拓扑时，由于拓扑序决定当前点之前所有点已经搜索过，所以它在新的灭绝树的倍增数组可以唯一确定。所以直接更新倍增数组。\(dad\)默认为-1。遍历\(u\)的食物\(v\),若当前点\(dad\)已经有值，则更新\(dad[i]=lca(dad[i],v)\)。

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=1e5+10,M=2e5+10,K=20;
struct edge{
    int v,nxt;
}e[M<<1];
int head[N],dad[N],ind[N],dep[N],fa[N][K],sz[N];
int cnt,n,u;
void add(int u,int v){
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}
vector<int> g[N];
queue<int> q;
int getlca(int u,int v){
    if(u==v) return u;
    if(dep[u]<dep[v]) swap(u,v);
    int k=dep[u]-dep[v];
    for(int i=0;i<K;++i){
        if((k>>i)&1) u=fa[u][i];
    }
    if(u==v) return u;
    for(int i=K-1;i>=0;--i){
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}
void dfs(int u,int p){
    sz[u]=1;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(v==p) continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
int main(){
    memset(head,-1,sizeof head);
    memset(dad,-1,sizeof dad);
    cnt=-1;
    scanf("%d",&n);
    for(int v=1;v<=n;++v){
        while(1){
            scanf("%d",&u);
            if(u==0) break;
            ++ind[v];
            g[u].push_back(v);
        }
    }


    for(int i=1;i<=n;++i){
        if(!ind[i]){
            q.push(i);
            dad[i]=0;
        }
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        add(u,dad[u]),add(dad[u],u);
        fa[u][0]=dad[u],dep[u]=dep[dad[u]]+1;
        for(int i=1;i<K;++i) fa[u][i]=fa[fa[u][i-1]][i-1]; 
        for(int i=0;i<g[u].size();++i){
            int v=g[u][i];
            if(dad[v]==-1){
                dad[v]=u;
            }else{
                dad[v]=getlca(u,dad[v]);
            }
            if(!(--ind[v])){
                q.push(v);
            } 
        }
    }
    dfs(0,0);
    for(int i=1;i<=n;++i){
        printf("%d\n",sz[i]-1);
    }
    return 0;
}