社区讨论
建议加强数据或时限,被水掉了
P6419[COCI 2014/2015 #1] Kamp参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhj9xwmo
- 此快照首次捕获于
- 2025/11/03 23:07 4 个月前
- 此快照最后确认于
- 2025/11/03 23:07 4 个月前
rt,multiset暴力模拟过了,最大点1.2s
CPP// Problem: P6419 [COCI 2014/2015 #1] Kamp
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6419
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define repr(i,a,b) for(int i=a;i<b;i++)
#define perp(i,a,b) for(int i=a;i>b;i--)
const int N=5e5+10;
#define int long long
int n,K;
vector<pair<int,int>> g[N];
multiset<int,greater<int>> st[N];
int sz[N],all[N],pri[N],prix[N];
void dfs1(int u,int fa){
sz[u]=1;prix[u]=pri[u];
if(pri[u])st[u].insert(0);
for(auto [v,w]:g[u]){
if(v!=fa){
dfs1(v,u);
sz[u]+=sz[v];
prix[u]+=prix[v];
if(prix[v]){
all[u]+=all[v];
all[u]+=w*2;
st[u].insert(*(st[v].begin())+w);
}
}
}
}
void swap(int u,int v,int w){
sz[u]-=sz[v];
prix[u]-=prix[v];
if(prix[v]){
all[u]-=all[v];
all[u]-=w*2;
st[u].erase(st[u].find(*(st[v].begin())+w));
}
sz[v]+=sz[u];
prix[v]+=prix[u];
if(prix[u]){
all[v]+=all[u];
all[v]+=w*2;
st[v].insert(*(st[u].begin())+w);
}
}
int ans[N];
void dfs2(int u,int fa){
ans[u]=all[u]-(*st[u].begin());
for(auto [v,w]:g[u]){
if(v!=fa){
swap(u,v,w);
dfs2(v,u);
swap(v,u,w);
}
}
}
signed main(){
cin>>n>>K;
rep(i,1,n-1){
int x,y,z;cin>>x>>y>>z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
rep(i,1,K){
int x;cin>>x;
pri[x]=1;
}
dfs1(1,0);
dfs2(1,0);
rep(i,1,n){
cout<<ans[i]<<endl;
}
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...