社区讨论

建议加强数据或时限,被水掉了

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 条回复,欢迎继续交流。

正在加载回复...