自动搬运

查看原文

来自洛谷，原作者为

	harmis_yz beiribaol，幻想，永恒。

搬运于2025-08-24 22:04:43，当前版本为作者最后更新于2024-11-24 10:19:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解摘自做题记录。

分析

不难发现，只有最多 $2m$ 个点是有用的。考虑先对这 $m$ 个点建立虚树。

对于一种行走方案，因为每条经过过的边都走了 $2$ 遍，所以就相当于将每条边的边权乘 $2$ 之后的边权和。下面任何表示的距离都是原树上距离的 $2$ 倍。

发现 $m$ 十分小，考虑暴力 DP。定义状态函数 $f_{i,j}$ 表示 $i$ 为根的子树中，花费 $j$ 的时间最多能得到的价值。因为我们是路径，所以需要保证我们选择的点形成连通块。那么对于 $u$ 来说，它就是必选的了。那么对于选择 $u$ 的一个儿子 $v$ 的子树，$u\to v$ 这条边也是必须经过的。有：$f_{u,x}=\max\limits_{y=0}^{x-w} f_{u,y}+f_{v,x-y-w}$。这个直接树上背包的时间复杂度是 $O(mV)$ 的。

然后对于询问，预处理前缀 $\max$ 可以做到 $O(1)$。算上建虚树的复杂度，就是 $O(m\log m+mV)$。

代码

il void dfs1(int u,int fa){
	dfn[u]=++cnt;
	f[u][0]=fa,dep[u]=dep[fa]+1;
	for(re int i=1;i<22;++i) f[u][i]=f[f[u][i-1]][i-1];
	for(auto v:e[u])
	if(v.x!=fa){
		dis[v.x]=dis[u]+2*v.y;
		dfs1(v.x,u);
	}
	return ;
} 
il int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(re int i=21;i>=0;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(re int i=21;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
il void build(){
	len=m;
	b[++len]=1;
	int len_=len;
	sort(b+1,b+len+1,[](int x,int y){
		return dfn[x]<dfn[y];
	});
	for(re int i=2;i<=len_;++i) b[++len]=lca(b[i],b[i-1]);
	sort(b+1,b+len+1,[](int x,int y){
		return dfn[x]<dfn[y];
	});
	len=unique(b+1,b+len+1)-(b+1);
	for(re int i=1;i<=len;++i) id[b[i]]=i,rev[i]=b[i];
	for(re int i=1;i< len;++i) E[id[lca(b[i],b[i+1])]].push_back({i+1,dis[b[i+1]]-dis[lca(b[i],b[i+1])]});
	return ;
}
il void dfs2(int u,int s){
	siz[u]=0;
	if(s==0){
		dp1[u][0]=val[rev[u]];
		for(auto v:E[u]){
			dfs2(v.x,s);
			for(re int w=min(M,siz[u]+v.y+siz[v.x]);w>=0;--w)
			for(re int x=0;x<=min(w-v.y,siz[u]);++x)
				dp1[u][w]=max(dp1[u][w],dp1[u][x]+dp1[v.x][w-v.y-x]);
			siz[u]+=v.y+siz[v.x];
		}
		for(re int i=1;i<=M;++i)
			dp1[u][i]=max(dp1[u][i],dp1[u][i-1]);
	}
	else{
		dp2[u][0]=val[rev[u]];
		for(auto v:E[u]){
			dfs2(v.x,s);
			for(re int w=min(M,siz[u]+v.y+siz[v.x]);w>=0;--w)
			for(re int x=0;x<=min(w-v.y,siz[u]);++x)
				dp2[u][w]=max(dp2[u][w],dp2[u][x]+dp2[v.x][w-v.y-x]);
			siz[u]+=v.y+siz[v.x];
		}	
		for(re int i=1;i<=M;++i)
			dp2[u][i]=max(dp2[u][i],dp2[u][i-1]);
	}
	return ;
}

il void solve(){
	n=rd,m=rd,t=rd;
	if(m<=20) M=100000;
	else M=100;
	for(re int i=1;i< n;++i){
		int u=rd,v=rd,w=rd;
		e[u].push_back({v,w}),
		e[v].push_back({u,w});
	}
	for(re int i=1;i<=m;++i){
		int x=rd;
		b[i]=x,val[x]=rd;
	}
	dfs1(1,0),build(),dfs2(1,(M==100));
	while(t--){
		int x=rd;
		if(M==100) printf("%lld\n",dp2[1][x]);
		else printf("%lld\n",dp1[1][x]);
	}
    return ;
}