ZJOI前来复习下点分板子~
考虑链的情况。从中点将链分为两段,此时最优解有三种情况:端点均在左侧,端点均在右侧,端点在两侧。前两者递归处理,后者处理中点到左侧点的距离,插入桶中,右侧点直接在桶中查询即可。
对于树,应用点分治。每次取重心,将子树依次插入桶中,并在桶中查询。注意重心也要插入桶中。
时间复杂度$\mathcal O(n\log n)$
const ll INF=1ll<<58;
/**********/
#define MAXN 200011
#define MAXK 1000011
struct edge
{
ll v,w,nxt;
}e[MAXN<<1|1];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,ll w)
{
++cnt;
e[cnt].v=v,e[cnt].w=w;
e[cnt].nxt=last[u],last[u]=cnt;
}
bool vis[MAXN];
ll size[MAXN];
void dfs1(ll u,ll fa)
{
size[u]=1;
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(vis[v]||v==fa)continue;
dfs1(v,u);
size[u]+=size[v];
}
}
ll dfs2(ll u,ll all,ll fa)
{
ll mson=0;
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(vis[v]||v==fa)continue;
if(size[v]>size[mson])mson=v;
}
if(size[mson]>all/2)return dfs2(mson,all,u);
return u;
}
std::vector<ll>a[MAXN];
ll sum[MAXN],len[MAXN];
void dfs3(ll u,ll fa,ll rt)
{
a[rt].push_back(u);
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(vis[v]||v==fa)continue;
sum[v]=sum[u]+e[i].w;
len[v]=len[u]+1;
dfs3(v,u,rt);
}
}
ll ans=INF,f[MAXK],n,k;
void solve(ll u)
{
dfs1(u,0);
u=dfs2(u,size[u],0);
//printf("visit %lld\n",u);
vis[u]=1,sum[u]=len[u]=0;
ll cnt=0;
a[++cnt].push_back(u);
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(!vis[v])sum[v]=e[i].w,len[v]=1,dfs3(v,u,++cnt);
}
for(ll i=1;i<=cnt;++i)
{
for(ll j=0;j<a[i].size();++j)
{
ll v=a[i][j];
if(sum[v]<=k)umin(ans,f[k-sum[v]]+len[v]);
}
for(ll j=0;j<a[i].size();++j)
{
ll v=a[i][j];
if(sum[v]<=k)umin(f[sum[v]],len[v]);
}
}
for(ll i=1;i<=cnt;a[i].clear(), ++i)
for(ll j=0;j<a[i].size();++j)
{
ll v=a[i][j];
if(sum[v]<=k)f[sum[v]]=INF;
}
//
for(ll i=last[u];i;i=e[i].nxt)
if(!vis[e[i].v])solve(e[i].v);
}
int main()
{
n=read(),k=read();
for(ll i=1;i<n;++i)
{
ll u=read()+1,v=read()+1,w=read();
adde(u,v,w),adde(v,u,w);
}
memset(f,0x3f,sizeof f);
solve(1);
printf("%lld",ans<=n?ans:-1ll);
return 0;
}
加油!!!!!!!!!!!!!1
wh大佬:大佬一路AK!
NOIP->ZJOI->NOI->IOI
%%%%%%加油!!!!!!!!!!!!!!!!
%%%加油~
zjoi 加油啊 !! !