题解 P7980【[JRKSJ R3] a question】
cyffff
·
·
题解
\text{Link}
\text{Subtask 1}
考虑直接建图再跑 $\text{Floyd}$，注意是答案需要取模，而不是取模后的最短路。时间复杂度 $O(n^3)$。
### $\text{Subtask 2}
考虑若 $\text T$ 中 $u,v$ 两点不相连，则 $\text G$ 中 $u,v$ 直接有边，距离可以 $\text {RMQ}-\text{LCA}$ $O(1)$ 求出。否则直接分类讨论，这个可以看后面的做法。这里可以直接搜两层，时间复杂度 $O(n^2)$。
### $\text{Subtask 3}
根节点显然没有贡献，直接忽略。考虑两点 $u,v,(u,v\ne1)$，它们肯定相邻，距离为 $w_{1,u}+w_{1,v}$，考虑每条边会被计算几次，所以答案为 $\displaystyle(n-2)\sum w$，时间复杂度 $O(n)$。
### $\text{Subtask 4}
问题即为树上每次转移只得走 $\ge2$ 格，求路径最小和，考虑分类算贡献：
1. $(u,v)\notin E$，设 $dep_u>dep_v$，则此部分贡献为 $\displaystyle\sum w\times siz_u\times(n-siz_u)
-
(u,v)\in E
考虑长这样，分类讨论：
- 向上走 2 格再向下走 3 格或者反过来，如图 1。
- 向下走 2 格再向上走 3 格再往下走 2 格，如图 2。注意需要存向下走两格的最小值和次小值，方便算贡献。
取 \min 即可，答案为两种贡献和再减掉多余的 \displaystyle \sum w 的贡献，时间复杂度 O(n)。
\text{Subtask 5}
上一个 $\text{Subtask}$ 中第二种情况由于每个点至多两个儿子只需维护向下 $2$ 格的 $\min$ 和 $\text{secmin}$ 就能计算，但是最小 $2$ 个值可能都是第一步走 $u$，所以需要维护**以 $v$ 向下走两格，且第一格不是 $u$ 的最小权值**，这点可以给 $v$ 的儿子编号，算出**以 $v$ 向下走两格，且第一格是 $u$ 的最小权值**，维护前后缀 $\min$，就能计算了，时间复杂度 $O(n)$。
这题思路简单，但实现细节繁多，并且有些卡常。
给一下我的代码：
```cpp
#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~