自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:34:52，当前版本为作者最后更新于2021-10-01 15:20:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$\text{Link}$

$\text{Subtask 1}$

$n\le 10^3$。

考虑直接建图再跑 $\text{Floyd}$，注意是答案需要取模，而不是取模后的最短路。时间复杂度 $O(n^3)$。

$\text{Subtask 2}$

$n\le 10^4$。

考虑若 $\text T$ 中 $u,v$ 两点不相连，则 $\text G$ 中 $u,v$ 直接有边，距离可以 $\text {RMQ}-\text{LCA}$ $O(1)$ 求出。否则直接分类讨论，这个可以看后面的做法。这里可以直接搜两层，时间复杂度 $O(n^2)$。

$\text{Subtask 3}$

$n\le 2\times 10^6$，树为菊花图。

根节点显然没有贡献，直接忽略。考虑两点 $u,v,(u,v\ne1)$，它们肯定相邻，距离为 $w_{1,u}+w_{1,v}$，考虑每条边会被计算几次，所以答案为 $\displaystyle(n-2)\sum w$，时间复杂度 $O(n)$。

$\text{Subtask 4}$

$n\le 2\times 10^6$，树为链。

问题即为树上每次转移只得走 $\ge2$ 格，求路径最小和，考虑分类算贡献：

1. $(u,v)\notin E$，设 $dep_u>dep_v$，则此部分贡献为 $\displaystyle\sum w\times siz_u\times(n-siz_u)$
2. $(u,v)\in E$

考虑长这样，分类讨论：

• 向上走 $2$ 格再向下走 $3$ 格或者反过来，如图 $1$。
• 向下走 $2$ 格再向上走 $3$ 格再往下走 $2$ 格，如图 $2$。注意需要存向下走两格的最小值和次小值，方便算贡献。

取 $\min$ 即可，答案为两种贡献和再减掉多余的 $\displaystyle \sum w$ 的贡献，时间复杂度 $O(n)$。

$\text{Subtask 5}$

$n\le 2\times 10^6$。

上一个 $\text{Subtask}$ 中第二种情况由于每个点至多两个儿子只需维护向下 $2$ 格的 $\min$ 和 $\text{secmin}$ 就能计算，但是最小 $2$ 个值可能都是第一步走 $u$，所以需要维护以 $v$ 向下走两格，且第一格不是 $u$ 的最小权值，这点可以给 $v$ 的儿子编号，算出以 $v$ 向下走两格，且第一格是 $u$ 的最小权值，维护前后缀 $\min$，就能计算了，时间复杂度 $O(n)$。

这题思路简单，但实现细节繁多，并且有些卡常。

给一下我的代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	
}
const int N=2e6+10,mod=1e9+7;
int n,cnt,head[N];
int son[N];
struct Edge{
	int to,nxt,w;
}a[N<<1],stc[N];
inline void add(int u,int v,int w){
	cnt++;
	a[cnt].to=v;
	a[cnt].nxt=head[u];
	a[cnt].w=w;
	head[u]=cnt;
	son[u]++;
}
int siz[N],dep[N],fa[N];
ll up[N],dw2[N],dw1[N],dw1s[N],dwp[N],go2[N],mdep[N];
inline void dfs1(int x,int f,int gf){
	siz[x]=1,dep[x]=dep[f]+1,mdep[x]=dep[x],fa[x]=f;
	dw1[x]=dw1s[x]=dw2[x]=go2[x]=2e16;
	dw2[gf]=min(dw2[gf],up[x]+up[f]);
	if(dw1[f]>up[x]){
		dw1s[f]=dw1[f];
		dwp[f]=x;
		dw1[f]=up[x];
	}else if(dw1s[f]>up[x]){
		dw1s[f]=up[x];
	}
	for(int i=head[x];i;i=a[i].nxt){
		int t=a[i].to;
		if(t==f) continue;
		up[t]=a[i].w;
		dfs1(t,x,f);
		mdep[x]=max(mdep[x],mdep[t]);
		siz[x]+=siz[t];
	}
}
ll *dw2h[N],tmp[N],pre[N],suf[N],pool[N<<2],*now=pool;
inline void dfs2(int x,int f){
	int sz=son[x],cnt=0;
	dw2h[x]=now,now+=sz+1;
	pre[0]=2e16,suf[sz+1]=2e16;
	for(int i=head[x];i;i=a[i].nxt)
		stc[cnt++]=a[i];
	reverse(stc,stc+cnt);
	for(int i=0;i<cnt;i++)
		if(stc[i].to!=f)
			tmp[i+1]=stc[i].w+dw1[stc[i].to];
		else
			tmp[i+1]=2e16;
	for(int i=1;i<=sz;i++)
		pre[i]=min(pre[i-1],tmp[i]);
	for(int i=sz;i>=1;i--)
		suf[i]=min(suf[i+1],tmp[i]);
	for(int i=1;i<=sz;i++)
		dw2h[x][i]=min(pre[i-1],suf[i+1]);
	for(int i=head[x];i;i=a[i].nxt){
		int t=a[i].to;
		if(t==f) continue;
		dfs2(t,x);
	}
	go2[x]=min(up[x]+up[f],dwp[f]==x?up[x]+dw1s[f]:up[x]+dw1[f]);
}
struct Tmp{
	int u,v,w,idu,idv;
}e[N];
ll ans1,ans2;
int main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
		e[i]={u,v,w,son[v],son[u]};
	}
	up[1]=up[0]=2e16;
	dfs1(1,0,0);
	dfs2(1,0);
	for(int i=1;i<n;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w,iu=e[i].idu,iv=e[i].idv;
		if(dep[u]<dep[v]) swap(u,v),swap(iu,iv);
		ans1=(ans1+1ll*w*siz[u]%mod*(n-siz[u]))%mod;
		ll tmp=2e16;
		if(mdep[u]-dep[u]>=2)
			tmp=min(tmp,dw2[u]);
		tmp=min(tmp,go2[u]+dw1[u]);
		tmp=min(tmp,go2[v]);
		tmp=min(tmp,dw2h[v][iu]);
		if(tmp<2e16)
			ans2=(ans2+2*tmp)%mod;
		else
			ans1=(ans1+mod-w)%mod;
	}
	write((ans1+ans2)%mod);
	flush();
}

再见 qwq~