树分治专题（学习笔记+做题记录）

void getroot(int u,int par){
    sz[u]=1,son[u]=0;
    for(int i=h[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(vis[v] || v==par) continue;
        getroot(v,u);
        sz[u]+=sz[v];
        son[u]=max(son[u],sz[v]); 
    }
    son[u]=max(son[u],sum-sz[u]);
    if(son[u]<maxson){
        maxson=son[u];
        rt=u;
    }
}

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;

const int maxn = 1000010;
const int INF = 1e9+7;

int n,k,ans=INF;
int sum,maxs;

int h[maxn],size;
struct E{
    int to,next,cost;
}e[maxn<<1];
void add(int u,int v,int w){
    e[++size].to=v;
    e[size].next=h[u];
    e[size].cost=w;
    h[u]=size;
}

int rt;
int vis[maxn],sz[maxn],son[maxn];
int d[maxn],s[maxn],f[maxn*10],c[maxn],ton[maxn*10],tot,cnt;

void getroot(int u,int par){
    sz[u]=1,son[u]=0;
    for(int i=h[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(v==par||vis[v]) continue;
        getroot(v,u);
        sz[u]+=sz[v];
        son[u]=max(son[u],sz[v]);
    }
    son[u]=max(son[u],sum-sz[u]);
    if(son[u]<maxs){
        maxs=son[u];
        rt=u;
    }
}

void dfs(int u,int par,int chang){
    d[u]=d[par]+chang;
    if(d[u]<=k) ton[++tot]=d[u];
    s[u]=s[par]+1;
    c[++cnt]=u;
    if(k>=d[u]) ans=min(ans,f[k-d[u]]+s[u]);
    for(int i=h[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(vis[v]||v==par) continue;
        dfs(v,u,e[i].cost);
    }
}

void solve(int u){
    vis[u]=1;
    tot=0; f[0]=0; d[u]=0; s[u]=0;
    for(int i=h[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(vis[v]) continue;
        cnt=0; 
        dfs(v,u,e[i].cost);
        
        for(int j=1;j<=cnt;++j){
            if(d[c[j]]>k) continue;
            f[d[c[j]]]=min(f[d[c[j]]],s[c[j]]);
        }
    }
    
    for(int i=1;i<=tot;++i) f[ton[i]]=INF;
    
    for(int i=h[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(vis[v]) continue;
        sum=sz[v],maxs=INF,rt=0;
        getroot(v,0);
        solve(rt);
    }
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); } return s*f;}

int main(){
    memset(h,-1,sizeof(h));
    n=read(),k=read();
    int u,v; ll w;
    for(int i=1;i<=1000000;++i) f[i]=INF;
    for(int i=1;i<n;++i){
        u=read(),v=read(),w=read();
        u++,v++;
        add(u,v,w),add(v,u,w);
    }
    
    sum=n; maxs=INF;
    getroot(1,0);
    
    solve(rt);
    
    printf("%d\n",ans==INF?-1:ans);
    
    return 0;
}