树链剖分、线段树、贪心

Solution 1：有显然的树剖加线段树做法，不知道 $O(n \log ^2 n)$ 能不能在时限内跑过 $n=5 \times 10^5$，算一下计算量大概是 $2 \times 10^8$ 等级，三秒是较为宽裕的（真的吗？）。

时间复杂度 $O(n \log^2 n)$。

需要卡常，应用的手法有两倍空间线段树，随机树剖根节点，快读。保留的手段是换用链式前向星建图，毕竟有点麻烦。

#include<bits/stdc++.h>
namespace sun{
    constexpr int RIN=1<<15;
    char quickchar(){
        static char buf[RIN],*be=buf,*ed=buf;
        if(be==ed) be=buf,ed=buf+fread(buf,1,RIN,stdin);
        return be==ed ? EOF:*be++;
    }
    template<typename T=int>
    T read(){
        T x=0;char ch=quickchar();
        while(!isdigit(ch)) ch=quickchar();
        while(isdigit(ch))
            x=x*10+ch-'0',ch=quickchar();
        return x;
    }
}
using namespace std;
using sun::read;
struct Segment{int w,m;}s[1'000'005];
int n,ans,pos,lim,d[500'005],f[500'005],w[500'005],dfn[500'005],eds[500'005],top[500'005],wson[500'005];
vector<int> e[500'005],v[500'005];
void fisdfs(int x,int las){
    w[x]=1,d[x]=d[las]+1,f[x]=las,wson[x]=0;
    for(int i:v[x]) if(i!=las){
        fisdfs(i,x),w[x]+=w[i];
        if(w[i]>w[wson[x]]) wson[x]=i;
    }
}
void secdfs(int x,int las){
    dfn[x]=++pos,top[x]=las;
    if(!wson[x]) return;
    secdfs(wson[x],las);
    for(int i:v[x]) if(i!=wson[x]&&i!=f[x]) secdfs(i,i);
}
void finddep(int x,int las){
    eds[x]=eds[las]+1,lim=max(lim,eds[x]);
    for(int i:v[x]) if(i!=las) finddep(i,x);
}
inline void mark(int u,int l,int r,int mid,int k){
    if(s[u].m+=k) s[u].w=r-l+1;
    else if(l==r) s[u].w=0;
    else s[u].w=s[mid*2].w+s[mid*2+1].w;
}
void update(int u,int l,int r,int ql,int qr,int k){
    int mid=(l+r)>>1;
    if(l>=ql&&r<=qr) return mark(u,l,r,mid,k);
    if(ql<=mid) update(mid*2,l,mid,ql,qr,k);
    if(qr>mid) update(mid*2+1,mid+1,r,ql,qr,k);
    mark(u,l,r,mid,0);
}
void updatepath(int x,int y,int k){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        update(1,1,n,dfn[top[x]],dfn[x],k);
        x=f[top[x]];
    }
    if(d[x]<d[y]) swap(x,y);
    update(1,1,n,dfn[y],dfn[x],k);
}
mt19937 sky(chrono::steady_clock::now().time_since_epoch().count());
void solution(){
    n=read(),ans=0,pos=0,lim=0;
    for(int i=1;i<=n-1;i++){
        int x=read(),y=read();
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int ro=sky()%n+1;
    fisdfs(ro,0),secdfs(ro,ro),finddep(1,0);
    for(int i=1;i<=n;i++) e[eds[i]].push_back(i);
    for(int i=lim;i>=1;i--){
        for(int j:e[i]) updatepath(1,j,1);
        ans=max(ans,s[1].w);
        for(int j:e[i]) updatepath(1,j,-1);
    }
    ans=n-ans;
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++) e[i].clear(),v[i].clear();
    for(int i=1;i<=n*2;i++) s[i].w=0,s[i].m=0;
}
int main(){
    for(int i=read();i;i--) solution();
    return 0;
}

Solution 2：优先考虑保留深度更大的叶子，每次加入深度等于当前指定深度 $d$ 的节点。

具体地，遍历所有深度等于 $d$ 的节点，如果节点未被加入就标记该节点为已经被加入，标记后后跳到该节点的父亲重复操作，如果当前节点是根或者已经被加入则终止加点操作。

维护当前已经被加入的节点数量 $sum$，保留的叶子深度从 $d$ 变为 $d-1$ 时加入所有深度为 $d-1$ 的节点，然后将 $sum$ 减去深度为 $d$ 的节点数量。

每个节点至多被加入一次，时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
vector<int> v[500'005],w[500'005];
int n,ans,cnt,lim,f[500'005];
bool on[500'005];
void dfs(int x,int las,int dep){
    f[x]=las,lim=max(lim,dep),w[dep].push_back(x);
    for(int i:v[x]) if(i!=las) dfs(i,x,dep+1);
}
void solution(){
    cin>>n,ans=0,cnt=0,lim=0;
    for(int i=1;i<=n-1;i++){
        static int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0,1);
    for(int i=lim;i>=1;i--){
        cnt-=w[i+1].size();
        for(int j:w[i]) while(j!=0&&!on[j]) ++cnt,on[j]=1,j=f[j];
        ans=max(ans,cnt);
    }
    ans=n-ans;
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++) on[i]=0,v[i].clear(),w[i].clear();
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}