社区讨论

莱德求助,Subtask #1全WA

P6419[COCI 2014/2015 #1] Kamp参与者 24已保存回复 24

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
24 条
当前快照
1 份
快照标识符
@lzdxv65k
此快照首次捕获于
2024/08/03 17:36
2 年前
此快照最后确认于
2025/01/14 21:34
去年
查看原帖
CPP
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const ll N=5e5+5;
struct node
{
	ll x,w;
};
ll n,x,y,w,vis[N],dp[N],len1[N],f[N],len2[N],up[N],k;
vector<node>c[N];; 
void dfs(ll cur,ll lst)
{
	for(ll i=0;i<c[cur].size();i++)
	{
		ll nxt=c[cur][i].x,w=c[cur][i].w;
		if(nxt!=lst)
		{
			dfs(nxt,cur);
			vis[cur]+=vis[nxt];
			if(vis[nxt]>0)
			{
				dp[cur]+=dp[nxt]+w*2;
				if(len1[nxt]+w>=len1[cur])
				{
					len2[cur]=len1[cur];
					len1[cur]=len1[nxt]+w;
				}
				else if(len1[nxt]+w>=len2[cur])
					len2[cur]=len1[nxt]+w;
			}
		}
	}
}
void jj(ll cur,ll lst)
{
	for(ll i=0;i<c[cur].size();i++)
	{
		ll nxt=c[cur][i].x,w=c[cur][i].w;
		if(nxt!=lst)
		{
			f[nxt]=(f[cur]-(vis[nxt]>0)*2*w)+(vis[cur]-vis[nxt]>0)*2*w;
			if(vis[cur]-vis[nxt]>0)
			{
				if(len1[nxt]+w==len1[cur]) 
					up[nxt]=max(up[cur],len2[cur])+w;
				else
					up[nxt]=max(up[cur],len1[cur])+w;
			}
			jj(nxt,cur); 
		}
	}
}
int main() {
  	cin>>n>>k;
	for(ll i=1;i<n;i++)
	{
		cin>>x>>y>>w;
		c[x].push_back((node){y,w});
		c[y].push_back((node){x,w});
	} 
	for(ll i=1;i<=k;i++)
	{
		cin>>x;
		vis[x]++;
	}
	dfs(1,0);
	f[1]=dp[1];
	jj(1,0);
	for(ll i=1;i<=n;i++)
		cout<<f[i]-max(len1[i],up[i])<<'\n'; 
  	return 0;
}

回复

24 条回复,欢迎继续交流。

正在加载回复...