Description

给定一棵有 $n$ 个点的以 $1$ 为根的树，在此问题中，叶子节点被定义为非根的度数为一的点。

每次操作可以删去一个叶子节点及其相连的边，你需要求出最小的操作次数，使得操作后所有叶子节点到根节点的距离相同。

Solution

考虑一条边什么情况下不会被删去。

对于 $(x,y)$ 这条边，设 $y$ 为深度较大的那个点，$z$ 为 $y$ 子树内深度最大的点，那么只要操作完后的叶子深度在 $[de{p}_y,de{p}_z]$ 范围内，那么这条边就不会被删去，对区间 $[de{p}_y,de{p}_z]$ 加 $1$ 即可，最后叶子深度则为所有可能深度中被加次数最大的那个深度，答案为边数减去其被加的次数。

发现这是区间加，单点查询，你可以用你喜欢的数据结构维护，如线段树、树状数组、分块等。

代码用线段树实现，复杂度 $O(n\log n)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls x<<1
#define rs x<<1|1
int t;
int n,tot;
int head[1000010],dep[1000010];
struct edge{int to,next;
}e[1000010];
void add(int x,int y){e[++tot]=edge{y,head[x]};head[x]=tot;
}
struct tree{int sum;
}tr[2000020];
void build(int x,int l,int r){tr[x].sum=0;if(l==r) return ;int mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);
}
void update(int x,int l,int r,int L,int R){if(l>=L&&r<=R){tr[x].sum++;return ;}int mid=l+r>>1;if(L<=mid) update(ls,l,mid,L,R);if(R>=mid+1) update(rs,mid+1,r,L,R);
}
int query(int x,int l,int r,int k){if(l==r) return tr[x].sum;int mid=l+r>>1,ans=tr[x].sum;if(k<=mid) return ans+query(ls,l,mid,k);else return ans+query(rs,mid+1,r,k);
}
int dfs(int x,int fax){dep[x]=dep[fax]+1;int maxn=dep[x];for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fax) continue;int z=dfs(y,x);update(1,1,n,dep[x]+1,z);maxn=max(maxn,z);}return maxn;
}
void init(){tot=0;for(int i=1;i<=n;i++){head[i]=0;}build(1,1,n);
}
void solve(){cin>>n;init();for(int i=1;i<n;i++){int x,y;cin>>x>>y;add(x,y),add(y,x);}dfs(1,0);int ans=0;for(int i=1;i<=n;i++){ans=max(ans,query(1,1,n,i));}cout<<n-1-ans<<'\n';
}
int main(){ios::sync_with_stdio(0);cin.tie(nullptr);cin>>t;while(t--){solve();}return 0;
}