bzoj3743 [COCI2015]Kamp

题意：一棵有边权树，要从一个点出发，遍历$m$个关键点。除了最后一个遍历的，都需要回到起点。对于$i∈[1,n]$，求出从该点出发完成任务的最短距离。 ------------ 考虑以一个关键点为根，把关键点建立一棵树 这样$i$号点的答案就是这棵树的边权和$\times 2+i$号点到这棵树的最短距离（记为$j$点）$-j$到树上一点的最远距离 因为树上的边至少走两次，从$i$到树上肯定要走最短距离，最后一个遍历的点不需要回到起点，所以一定是把距离最远的点作为终点 所以可以用$4$个$dfs$ - 求出每个点是否在新建的树上，并计算树的边权和$(on,sum)$ - 找到每个点到树的最短距离以及最近点$(dis,nrp)$ - 找到树上每个点对应的最长链和次长链$(f,g)$ - 求出树上每个点到其他点的最远距离$(d)$ ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=5e5+5; struct node { int to,nxt,dis; }edge[N<<1]; int n,m,num,head[N],on[N],rt,nrp[N],son[N]; ll sum,f[N],g[N],dis[N],d[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to,int dis) { edge[++num]=(node){to,head[from],dis}; head[from]=num; } bool dfs1(int k,int fa) { for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==fa) continue; if (dfs1(v,k)) on[k]=1,sum+=edge[i].dis; } return on[k]; } void dfs2(int k,int fa) { if (on[k]) nrp[k]=k; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==fa) continue; if (!on[v]) nrp[v]=nrp[k],dis[v]=dis[k]+edge[i].dis; dfs2(v,k); } } void dfs3(int k,int fa) { for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==fa||!on[v]) continue; dfs3(v,k); ll now=f[v]+edge[i].dis; if (now>f[k]) g[k]=f[k],f[k]=now,son[k]=v; else g[k]=max(g[k],now); } } void dfs4(int k,int fa,ll dt) { d[k]=max(f[k],dt); for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==fa||!on[v]) continue; dfs4(v,k,max(dt,(v==son[k]?g[k]:f[k]))+edge[i].dis); } } int main() { n=read(),m=read(); for (reg int i=1;i<n;i++) { int x=read(),y=read(),z=read(); add_edge(x,y,z); add_edge(y,x,z); } for (reg int i=1;i<=m;i++) on[rt=read()]=1; dfs1(rt,0); dfs2(rt,0); dfs3(rt,0); dfs4(rt,0,0); for (reg int i=1;i<=n;i++) printf("%lld\n",sum*2+dis[i]-d[nrp[i]]); return 0; } ```