点权 题解

题解提供两种写法，先讲贪心写法。

这虽然是一个树上的题目，但是在图上它也同样可以写。

因为这实质上是最短路模型。

与一般最短路不同的是，这题一个点要从两个点转移过来。

我们假设$ii$的答案是从$j,kj,k$转移过来的，$an{s}_{i}ans\_i$为$ii$号结点点权变为2的答案。

那么有，若$ii$的度数小于$22$,则$an{s}_i=0ans\_i=0$,$an{s}_i=an{s}_j+an{s}_k+w1+w2ans\_i=ans\_j+ans\_k+w1+w2$,其中$w1,w2w1,w2$表示对应两条边的边权。

由于边权非负，那么我们有$an{s}_i>an{s}_j\mathrm{且}an{s}_i>an{s}_{k}ans\_i>ans\_j且ans\_i>ans\_k$

所以我们开一个堆，把所有的叶子都丢进去，然后不断拿出堆中答案最小的点去更新它相邻的点。

复杂度和迪杰斯特拉一样都是$O(n\ast logn)O(n*logn)$的

#include<bits/stdc++.h>
using namespace std;
#define M 100005
struct hh{
	int p,w;
	bool operator<(hh x)const{
		return w>x.w;
	}
};
vector<hh>d[M];
int n;
int mi1[M],mi2[M],ans[M],deg[M];
priority_queue<hh>q;
void merge(int x,int w){
	if(w<mi1[x])mi2[x]=mi1[x],mi1[x]=w;
	else if(w<mi2[x])mi2[x]=w;
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v,w;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		d[u].push_back((hh){v,w});
		d[v].push_back((hh){u,w});
		deg[u]++;deg[v]++;
	}
	memset(mi1,63,sizeof(mi1));memset(mi2,63,sizeof(mi2));memset(ans,63,sizeof(ans));
	for(int i=1;i<=n;++i)if(deg[i]<=1)q.push((hh){i,0}),ans[i]=mi1[i]=mi2[i]=0;
	while(!q.empty()){
		int p=q.top().p,w=q.top().w;q.pop();
		if(w>ans[p])continue;
		for(int i=0;i<(int)d[p].size();++i){
			int v=d[p][i].p;
			merge(v,w+d[p][i].w);
			if(mi1[v]+mi2[v]<ans[v])ans[v]=mi1[v]+mi2[v],q.push((hh){v,ans[v]});
		}
	}
	for(int i=1;i<=n;++i)if(ans[i]>1e9)ans[i]=-1;
	for(int i=1;i<=n;++i)printf("%d ",ans[i]);
}

换根DP写法：

对于一个点，如果只考虑子树的情况，那么它的答案一定是从最小的两个儿子转移过来的。

然后需要解决的就是，一个点可能从父亲转移过来，那么我们先把每个点只考虑子树内的答案跑出来，然后用换根DP求父亲的贡献。

两遍dfs，第一遍求出每个点从子孙转移来、使得点权 $+1+1$ 的前三小消耗；第二遍求出从祖先转移来，使得点权$+1+1$的最小消耗

最后对于每一个点选择两个消耗最小的，就是答案

#include<bits/stdc++.h>
using namespace std;
#define M 100005
#define ckmi(a,b) ((a>b)&&(a=b))
struct hh{
	int p,w;
};
vector<hh>d[M];
int dp[M],mx1[M],mx2[M],mx3[M],inf=(1e9)+100000,ans[M];
void merge(int x,int t){
	if(t<mx1[x])mx3[x]=mx2[x],mx2[x]=mx1[x],mx1[x]=t;
	else if(t<mx2[x])mx3[x]=mx2[x],mx2[x]=t;
	else if(t<mx3[x])mx3[x]=t;
}
void dfs(int x,int f){
	dp[x]=inf;mx1[x]=inf;mx2[x]=inf;mx3[x]=inf;
	if(d[x].size()<=1)dp[x]=0;
	for(int i=0;i<(int)d[x].size();++i){
		int v=d[x][i].p;
		if(v==f)continue;
		dfs(v,x);
		merge(x,dp[v]+d[x][i].w);//这里维护出前三小的叶子
	}
	ckmi(dp[x],mx1[x]+mx2[x]);//只考虑子树内的答案。
}
void Dfs(int x,int f){
	ans[x]=dp[x];ckmi(ans[x],mx1[x]+mx2[x]);
	for(int i=0;i<(int)d[x].size();++i){
		int v=d[x][i].p;
		if(v==f)continue;
		int t=dp[x];dp[x]=inf;//这是当x失去v这个儿子时的DP值
		if(d[x].size()<=1)dp[x]=0;//父亲可能是叶子
		int s=dp[v]+d[x][i].w;
		if(s==mx1[x])ckmi(dp[x],mx2[x]+mx3[x]);
		else if(s==mx2[x])ckmi(dp[x],mx1[x]+mx3[x]);
		else ckmi(dp[x],mx1[x]+mx2[x]);//这是把父亲换到儿子的位置
		merge(v,dp[x]+d[x][i].w);//合并
		Dfs(v,x);dp[x]=t;
	}
}
void rd(int &x){
	x=0;int c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
}
int main(){
	int n;rd(n);
	for(int i=1,u,v,w;i<n;++i){
		rd(u);rd(v);rd(w);
		d[u].push_back((hh){v,w});
		d[v].push_back((hh){u,w});
	}
	dfs(1,0);ans[1]=dp[1];Dfs(1,0);
	for(int i=1;i<=n;++i)if(ans[i]==inf)ans[i]=-1;
	for(int i=1;i<=n;++i)printf("%d ",ans[i]);
}