点权

NC229893. 点权

描述

你有一棵 $n$ 个点的树，每个点的点权可能是 $\{-1, 0, 1, 2\}$ ，初始均为 $0$ ，每条边均有一个正整数边权。现在你能进行两种操作：

1. 将一个度小于 $2$ 且权为 $0$ 的点点权变为 $2$ 。该操作没有消耗。

2. 使一个点权为 $2$ 的点点权变为 $-1$ ，并且让一个与其通过一条边连接，且点权 $\in \{0, 1\}$ 的点点权 $+1$ 。该操作的消耗为对应边边权。

对于每个点，求出让其点权变为 $2$ 的最小消耗。如果不可能做到，输出 $-1$ 。

输入描述

第一行，一个正整数  表示点数。

接下来  行，每行三个正整数 ，表示  和  之间有一条权值为  的边连接。()

对于  的数据，。

输出描述

一行  个整数，第  个数表示让  号节点的点权变为  的最小消耗。

示例1

输入:

输出:

10 7 0 0 0

示例2

输入:

输出:

0 -1 -1 3 0 0

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 94ms, 内存消耗: 10900K, 提交时间: 2021-12-10 22:41:35

#include<bits/stdc++.h>
using namespace std;

int i,j,k,n,m,t,a[200500],f[200500],w,b[200500];
bool vis[200500];
vector<pair<int,int> > v[200500];

int main(){
	ios::sync_with_stdio(0);
	priority_queue<pair<int,int> >q;
	cin>>n;
	if(n==1){cout<<0;return 0;}
	for(i=1;i<n;i++){
		cin>>j>>k>>w;
		v[j].push_back({k,w});
		v[k].push_back({j,w});
		a[j]++;a[k]++;
	}
	for(i=1;i<=n;i++){
		if(a[i]==1){
			vis[i]=1;
			for(auto [j,k]:v[i]){if(vis[j]){continue;}q.push({-k,j});}
		}
	}
	while(!q.empty()){
		auto [x,y]=q.top();q.pop();
		if(vis[y])continue;
		x=-x;f[y]+=x;b[y]++;
		if(b[y]==2){
			vis[y]=1;
			for(auto [i,j]:v[y]){if(vis[i]){continue;}q.push({-f[y]-j,i});}
		}
	}
	for(i=1;i<=n;i++)cout<<(((!vis[i])?-1:f[i]))<<' ';
}