用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day3

这是本文档旧的修订版!


CCPC Wannafly Camp Day3

G. 火山哥周游世界

题意

给定一棵边权树和 $k$ 个关键点,问从第 $i(1\le i\le n)$ 点出发经过所有关键点的最短路程。

题解

不难发现答案为第 $i$ 个点与所有关键点构成的生成树的边权和的两倍 $-$ 第 $i$ 个点到最远关键点的距离。

换根 $\text{dp}$ 维护每个结点的生成树边权和,每个结点子树方向的最远关键结点、次远关键结点以及根节点方向的最远关键结点即可。

时间复杂度 $O(n)$。

查看代码

查看代码

const int MAXN=5e5+5;
LL inf=1e15;
struct Edge{
	int to,w,next;
}edge[MAXN<<1];
int head[MAXN],edge_cnt,k;
void Insert(int u,int v,int w){
	edge[++edge_cnt]=Edge{v,w,head[u]};
	head[u]=edge_cnt;
}
LL f[MAXN],dp[MAXN][3],ans[MAXN];
int sz[MAXN],hson[MAXN];
void dfs1(int u,int fa){
	hson[u]=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v])f[u]+=f[v]+edge[i].w*2;
		if(dp[v][0]+edge[i].w>dp[u][0]){
			hson[u]=v;
			dp[u][1]=dp[u][0];
			dp[u][0]=dp[v][0]+edge[i].w;
		}
		else if(dp[v][0]+edge[i].w>dp[u][1])
		dp[u][1]=dp[v][0]+edge[i].w;
	}
}
void dfs2(int u,int fa){
	ans[u]=f[u]-max(dp[u][0],dp[u][2]);
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		if(sz[v]==0)
		f[v]=f[u]+edge[i].w*2;
		else if(sz[v]!=k)
		f[v]=f[u];
		if(v==hson[u])
		dp[v][2]=edge[i].w+max(dp[u][1],dp[u][2]);
		else
		dp[v][2]=edge[i].w+max(dp[u][0],dp[u][2]);
		dfs2(v,u);
	}
}
int main()
{
	int n=read_int();
	k=read_int();
	_for(i,1,n){
		int u=read_int(),v=read_int(),w=read_int();
		Insert(u,v,w);
		Insert(v,u,w);
	}
	_rep(i,1,n)
	dp[i][0]=dp[i][1]=dp[i][2]=-inf;
	_for(i,0,k){
		int u=read_int();
		dp[u][0]=dp[u][1]=dp[u][2]=0;
		sz[u]=1;
	}
	dfs1(1,0);
	dfs2(1,0);
	_rep(i,1,n)
	enter(ans[i]);
	return 0;
}
2020-2021/teams/legal_string/jxm2001/contest/ccpc_wannafly_winter_camp_day3.1619874209.txt.gz · 最后更改: 2021/05/01 21:03 由 jxm2001