bzoj3743 [COCI2015]Kamp

2018-11-07 15:47:49

• 求出每个点是否在新建的树上，并计算树的边权和 $(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;
}
• star
首页