QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#698893#5313. Please Save PigelandfrogmanRE 0ms24616kbC++141.6kb2024-11-01 22:56:322024-11-01 22:56:33

Judging History

你现在查看的是最新测评结果

  • [2024-11-01 22:56:33]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:24616kb
  • [2024-11-01 22:56:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 500010
#define int long long
int sz[N],L[N],R[N],w[N],book[N],a[N],t[N<<2];
vector<pair<int,int> > g[N];
int n,k,sum,ans=1e18;
void build(int l,int r,int now){
	if(l==r){
		t[now]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,now<<1);
	build(mid+1,r,now<<1|1);
	t[now]=__gcd(t[now<<1],t[now<<1|1]);
}
void upt(int l,int r,int x,int y,int now){
	if(x<1||x>k){
		return;
	}
	if(l==r){
		t[now]+=y;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid){
		upt(l,mid,x,y,now<<1);
	}else{
		upt(mid+1,r,x,y,now<<1|1);
	}
	t[now]=__gcd(t[now<<1],t[now<<1|1]);
}
void dfs(int x,int fa){
	if(book[x]){
		sum+=w[x];
		L[x]=++L[0];
		a[L[0]]=w[x];
	}
	for(auto b: g[x]){
		int v=b.first;
		int c=b.second;
		if(v==fa){
			continue;
		}
		w[v]=w[x]+c;
		dfs(v,x);
		L[x]=min(L[x],L[v]);
	}
	R[x]=L[0];
}
void Dfs(int x,int fa,int s){
	ans=min(ans,s/abs(t[1]));
	for(auto b: g[x]){
		int v=b.first;
		int c=b.second;
		if(v==fa){
			continue;
		}
		upt(1,k,1,c,1);
		upt(1,k,L[v],-c-c,1);
		upt(1,k,R[v]+1,c+c,1);
		Dfs(v,x,s+(k-2*(R[v]-L[v]+1))*c);
		upt(1,k,1,-c,1);
		upt(1,k,L[v],+c+c,1);
		upt(1,k,R[v]+1,-c-c,1);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=k;++i){
		int x;
		cin>>x;
		book[x]=1;
	}
	for(int i=1;i<n;++i){
		int x,y,z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	for(int i=1;i<=n;++i){
		L[i]=1e9;
	}
	dfs(1,0);
	for(int i=L[0];i;--i){
		a[i]-=a[i-1];
	}
	build(1,k,1);
	Dfs(1,0,sum);
	cout<<ans*2;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 24616kb

input:

5 3
3 4 5
1 2 2
2 3 4
2 5 4
3 4 6

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 0ms
memory: 15392kb

input:

10 3
1 7 10
7 6 3
1 8 3
3 6 3
8 6 2
4 1 1
10 6 4
2 8 3
9 10 3
5 10 3

output:

24

result:

ok 1 number(s): "24"

Test #3:

score: -100
Runtime Error

input:

1 1
1

output:


result: