自动搬运

查看原文

来自洛谷，原作者为

	光明正大 AFO

搬运于2025-08-24 22:16:58，当前版本为作者最后更新于2020-02-11 15:24:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

二分答案！！！

比赛时看到此题仔细琢磨，感觉和NOIP 2018赛道修建有些类似

都是在分一定段的前提下使某个值尽可能地小（大）。

二分答案：显然是对需要时间最长的人所需要的时间，即要求的答案 $ans$ 进行二分。

如果 $ans$ 越大，那么每个人可以访问到的节点就一定不会更少，需要的人力就越少，答案具有可二分性。

所以对于每个$mid$，我们求出所需要的的人数$x$，

如果$x$ <= $k$，说明在规定时间内完成任务，则接着在左半边找；

如果$x$ > $k$，说明在规定时间完不成任务，则接着在右半边找。

问：在每次$check()$时，我们想让一个人到达尽可能多的叶子节点，如何快速的求出从叶子s能到达的距s最远的节点呢？

答：二分答案！

这一点与赛道修建比较相似，在总的二分答案的check中再次二分。

设 $s$ 走到 $t$ 花费时间 $time$，

若 $time$ <= $ans$ 则说明时间没用完，在 $t$ 到 $tot$之间找；

若 $time$ > $ans$ 则说明时间不够用，在$s$ 到 $tot$之间找。

显然在寻找最远能走到的叶子的过程中，也具有可二分性。

这里其实还有一个小问题：

如何快速地（$O(1)$）求出两个叶子之间的距离呢？

设 $dis_i$ 表示 $i$ 到 $root$ 的距离，

对于树上任意两点 $i$ , $j$ ，

它们之间的距离为 :

$dis_i$ + $dis_j$ - 2*$dis_{LCA(i,j)}$

$dis$ 数组的求解可在LCA的预处理中进行。

设 $s_i$ 表示从第一个叶子节点到第 $i$ 个节点间的距离，

若一个人把 $i$ 到 $j$ 之间的点都访问了一遍，那么他所需的时间为：（自己画个图就能明白了其实是我懒得画图了）

$s_j-s_i+dis_i+dis_j$

$s$ 数组也可以快速提前处理。

也许有人还有问题，如何保证叶子结点的顺序呢？

题目中有一句话：“本质上，题目给出的树就是住址构成的 字典树/Trie树 ”。

这就保证了按照读入的顺序跑一遍 $DFS$ 依次访问到的是编号从大到小的叶子结点(因为链式前向星是倒序遍历的，不过正倒并不影响)。

我在程序另开一个数组 $st$ 其中 $st_i$ 表示从大到小第i个叶子结点的编号：

设叶子结点为 $m$ (实际上最多为 $n-1$ )，值域为 $w$，

总复杂度为 $O(k*log(w)*log(m))$

下面是我的代码：仅供参考，略有压行，大佬不喜勿喷

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;
struct EDGE{int to,next;ll w;} e[maxn<<1];
bool nl[maxn];//not leaf 
int n,m,k,root,cnt,dep[maxn],fa[maxn][22],Log2[maxn],head[maxn];
ll dis[maxn],s[maxn];
void add(int u,int v,ll w)
{e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;}
inline void dfs(int u,int f)
{
	dep[u]=dep[f]+1;fa[u][0]=f;
	for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].next) {
		if(e[i].to!=f) nl[u]=1,
			dis[e[i].to]=dis[u]+e[i].w,dfs(e[i].to,u);
	}
}
inline int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]) x=fa[x][Log2[dep[x]-dep[y]]-1];
	if(x==y) return x;
    for(int k=Log2[dep[x]]-1;k>=0;k--) if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
    return fa[x][0];
}
int st[maxn],tot;//st[]:存叶子几点的编号 
inline void DFS(int u)//找到所有叶子结点 
{
	for(int i=head[u];i;i=e[i].next) 
		if(e[i].to!=fa[u][0]) DFS(e[i].to);
	if(!nl[u]) st[++tot]=u;
}
inline ll calc(int u,int v) {return s[v]+dis[st[v]]-s[u]+dis[st[u]];}
inline int erfen(int s,ll x)//对能走到的位置二分 
{
	int L=s,R=tot,res=s-1;
	while(L<=R) {
		int mid=(L+R)>>1;
		if(calc(s,mid)<=x) res=mid,L=mid+1;
		else R=mid-1;
	}
	return res;
}
inline bool check(ll x)
{
	int last=0,temp=0;
	for(int i=1;i<=k;i++) {
		temp=erfen(last+1,x);
		if(temp==last) return 0;
		if(temp>=tot) return 1;
		last=temp;
	}
	return temp==tot;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1,x,y,w;i<n;i++) {
    	scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);add(y,x,w);
	}
    dfs(1,0);DFS(1);
    for(int i=1;i<=n;i++) Log2[i]=Log2[i-1]+(1<<Log2[i-1]==i);
    for(int i=2;i<=tot;i++) //求解s数组 
    	s[i]=s[i-1]+dis[st[i]]+dis[st[i-1]]-dis[LCA(st[i-1],st[i])]*2LL;
    ll l=1,r=1LL<<60,ans=1LL<<60;
    while(l<=r) {//对答案二分 
    	ll mid=(l+r)>>1;
    	if(check(mid)) ans=mid,r=mid-1;
    	else l=mid+1;
	}
	printf("%lld",ans);
    return 0;
}

代码中有些小细节还需特别注意， 总的来说是一道很不错的二分答案的题目