社区讨论
莱德求助,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 条回复,欢迎继续交流。
正在加载回复...