牛客练习赛93-C题-点权_随笔

牛客练习赛93-C题-点权

ps:这道题当时赛场上脑抽想到拓扑排序去了，这题并不能用拓扑排序写，因为这题要求将点权变成2的最小花费，而这最小花费是与边权有关系的，而与深度没关系。

如何想到树形dp?:题目已经明说这是一颗树了，首先我们不难看到更新都是从叶结点向上传递，这就满足了dp的无后效性，又因为不难发现每一个点作为根节点结果都不同，于是我们不难想到一个o(n*n)的算法。

朴素算法o(n*n):枚举每一个结点作为根节点，然后进行树形dp，每个结点调最小的那个值即可。

改进-换根法o(n):不难发现以上模型就是换根法的模型，我们可以将其优化成o(n)，即两次进行两次树形dp。

第一次树形dp(从底向上):依据经验我们设dp[i]为结点i由子结点更新的最小花费

状态转移方程:

第二次树形dp(从上向底):依据经验我们设f[i]为结点的最小花费

状态转移方程:

其实某一点一定是从子节点或者父亲结点更新过来的，这点也能看出是换根法。

AC代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int number=1e6+5;
template
inline void read(T &x){
	x=0;
	int f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	x*=f;
}
template
inline void write(T x){
	if(x<0){putchar('-');x=~x+1;}
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
typedef struct node{
	ll from,to,dist;
	node(ll a,ll b,ll c):from(a),to(b),dist(c){}
}node;
vectoredge;
vectorg[number];
ll dp[number],n,f[number],v[number],m1[number],m2[number],al[number],root;
void add(ll a,ll b,ll c){
	edge.push_back(node{a,b,c});
	g[a].push_back(edge.size()-1);
	edge.push_back(node{b,a,c});
	g[b].push_back(edge.size()-1);
}
void dfs_dp(ll step){
	v[step]=1;
	bool flag=false;
	for(ll i=0;i<(ll)g[step].size();i++){
		node y=edge[g[step][i]];
		if(v[y.to]) continue;
		dfs_dp(y.to);
		flag=true;
		ll a=dp[y.to]+y.dist;
		if(a<=m1[step]){m2[step]=m1[step],m1[step]=a;}
		else if(a1){root=i;break;}
	}
	dfs_dp(root);
	memset(v,0,sizeof(v));
	f[root]=dp[root];
	dfs_f(root);
	if(n==1){
		cout<<0<=0x3f3f3f3f) cout<<-1<<' ';
		else cout< 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5658697.html

牛客练习赛93-C题-点权

发表评论

评论列表（0条）