SP2420 solution

给定一颗 \(n\) 个节点的树，在树上找一条长为 \(l\) 的链，使得树上每个节点到链的距离之和最短，求这个最短距离。

题解

首先我们思考多个点到一个点距离和怎么计算。可以考虑使用树形 DP，将这个点作为跟，记录 \(siz_u\) 为 \(u\) 点子树的大小，\(sum_u\) 为 \(u\) 点子树中的点到它的距离和。则如果存在 \(v\) 是 \(u\) 的儿子，可以得到转移

不妨设这条链过根节点，那么如果点 \(v\) 在链上，则答案减小 \(siz_v\)，因为 \(v\) 子树内的点（包括它自己），不用走 \(v\to u\) 这条边了，而这条边会被计算 \(siz_v\) 次。对于 \(v\) 的子节点这一结论同样成立。

假如这题让我们求的不是一条链，而是一个点，那么这个点就是这颗树的重心。

证明：

对于假设重心为 \(u\) 且是树的根节点，在重心旁的点为 \(v\)，这是一个换根的过程，定义 \(f_i\) 表示 \(i\) 为根节点时各点到它距离和。

那么

\[f_v=f_u+n-2\times siz_v \]

因为 \(u\) 是重心，所以 \(2\times siz_v\leq n\)，所以 \(f_v\geq f_u\)。

将这个结论推广到所有节点，假设 \(w\) 是 \(v\) 节点的儿子，必然 \(siz_w<siz_v\)，自然 \(f_w> f_v\)。

我们将这个过程搬到链上，如图。

假设绿色链过重心，红色链不过重心。注意此时重心是根。

那么显然红色链和绿色链公共的部分的子节点的答案不变，而因为重心的性质，\(siz_v\leq siz_w\leq \frac{n}{2}\leq siz_u-siz_w\)，那么答案变大 \(siz_u-siz_w-siz_v\geq 0\)。

所以我们不严谨地说明了这条链必须经过重心。

实现

树形 DP 先求出树的重心，然后以重心为根节点求出每个点到根（不包含根）的路径上的 \(siz\) 和，同时求出每个点的深度（假设根节点深度为 \(0\)）。

然后答案就是两个在不同子树内的点，他们的深度之和小于等于 \(l\)，他们 \(siz\) 和的和。

注意如果 \(l\) 很大，那么如果用桶的话可能会出现 \(l\) 减去一个点的深度后桶内没有值的情况，于是我们用树状数组统计前缀最大值即可。

时间复杂度 \(O(n\log l)\)。

int n,L,root,fa[N];
ll sum[N],siz[N],fiz[N];
vector<int>edge[N];
void getroot(int u,int f){
	siz[u]=1,fiz[u]=0;
	for(auto v:edge[u]){
		if(v==f)continue;
		getroot(v,u);
		siz[u]+=siz[v];
		fiz[u]=max(fiz[u],siz[v]);
	}fiz[u]=max(fiz[u],n-siz[u]);
	if(fiz[u]<fiz[root])root=u;
}
int lis[N],tot,dep[N];
void dfs(int u,int f){
	siz[u]=1,sum[u]=0;
	for(auto v:edge[u]){
		if(v==f)continue;
		dfs(v,u);
		siz[u]+=siz[v];
		sum[u]+=sum[v]+siz[v];
	}
}
void getlis(int u,int f,int d,ll pre){
	siz[u]+=pre;dep[u]=d;lis[++tot]=u;
	for(auto v:edge[u]){
		if(v==f)continue;
		getlis(v,u,d+1,siz[u]);
	}
}
struct BIT{
	ll c[102];
	inline void init(){memset(c,0,sizeof(c));}
	inline int lowbit(int x){return x&-x;}
	inline void update(int i,ll v){++i;for(;i<=L+1;i+=lowbit(i))c[i]=max(c[i],v);}
	inline ll getmaxv(int i){ll ans=0;++i;for(;i;i-=lowbit(i))ans=max(ans,c[i]);return ans;}
}c;
inline ll solve(){
	int u=root;ll ans=0;
	dfs(u,0);c.init();
	for(auto v:edge[u]){
		tot=0;getlis(v,u,1,0);
		for(int i=1;i<=tot;++i)
			if(dep[lis[i]]<=L)ans=max(ans,siz[lis[i]]+c.getmaxv(L-dep[lis[i]]));
		for(int i=1;i<=tot;++i)
			if(dep[lis[i]]<=L)c.update(dep[lis[i]],siz[lis[i]]);
	}
	return sum[u]-ans;
}
int main(){
	int T=read();
	while(T--){
		n=read(),L=read();
		for(int i=0;i<=n;++i)
			edge[i].clear();
		for(int i=1;i<n;++i){
			int u=read()+1,v=read()+1;
			edge[u].push_back(v);
			edge[v].push_back(u);
		}
		fiz[root=0]=INF;
		getroot(1,0);
		printf("%lld\n",solve());
	}
	return 0;
}

后记

感觉生了点病，但是不能及时去医院，写道 hospital 题。感谢 Kzos_017 和 ctldragon 对做此题的帮助。

这里贴一下队爷 Kzos_017 的做法。（不懂）