QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235878#5313. Please Save Pigelandushg8877#WA 3ms23292kbC++202.8kb2023-11-03 11:49:312023-11-03 11:49:32

Judging History

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

  • [2023-11-03 11:49:32]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:23292kb
  • [2023-11-03 11:49:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=5e5+5;
int siz[MAXN];ll sum[MAXN],rep[MAXN],f[MAXN];bool mark[MAXN];
// f 表示内部差的 gcd 
int n,k;
int eu[MAXN],ev[MAXN],ew[MAXN];ll ans=5e18;
vector<int> edg[MAXN];
int gcd(int x,int y){
	if(!x||!y) return x|y;
	else if(x%y==0) return y;
	else return gcd(y,x%y);
}
void dfs(int u,int fa){
	rep[u]=-1;siz[u]=0;sum[u]=0;
	if(mark[u]){
		siz[u]=1;rep[u]=0;
	}
	for(int i:edg[u]){
		int v=(eu[i]==u?ev[i]:eu[i]);
		if(v==fa) continue;
		dfs(v,u);
		siz[u]+=siz[v];sum[u]+=sum[v]+siz[v]*ew[i];
		f[u]=gcd(f[u],f[v]);
		if(rep[v]!=-1){ 
			if(rep[u]!=-1) f[u]=gcd(f[u],abs(rep[u]-(rep[v]+ew[i])));
			else rep[u]=rep[v]+ew[i];
		} 
	}
//	cout<<"get "<<u<<" "<<f[u]<<' '<<rep[u]<<endl; 
	return;
}
void root(int u,int fa){
	rep[u]=-1;siz[u]=0;sum[u]=0;f[u]=0;
	if(mark[u]){
		siz[u]=1;rep[u]=0;
	}
	for(int i:edg[u]){
		int v=(eu[i]==u?ev[i]:eu[i]);
		siz[u]+=siz[v];sum[u]+=sum[v]+siz[v]*ew[i];
		f[u]=gcd(f[u],f[v]);
		if(rep[v]!=-1){ 
			if(rep[u]!=-1) f[u]=gcd(f[u],abs(rep[u]-(rep[v]+ew[i])));
			else rep[u]=rep[v]+ew[i];
		} 
	}
	ans=min(ans,sum[u]/gcd(rep[u],f[u]));
//	cout<<"Get "<<u<<" "<<sum[u]<<' '<<gcd(rep[u],f[u])<<endl;
//	for(int i=1;i<=n;i++) cout<<rep[i]<<' ';cout<<endl;
//	for(int i=1;i<=n;i++) cout<<f[i]<<' ';cout<<endl;
	int e=edg[u].size();
	vector<ll> pf(e),sf(e),pr(e),sr(e);
	rep[u]=-1;f[u]=0;
	if(mark[u]){
		siz[u]=1;rep[u]=0;
	}
	for(int id=0;id<e;id++){
		int i=edg[u][id];
		int v=(eu[i]==u?ev[i]:eu[i]);
		f[u]=gcd(f[u],f[v]);
		if(rep[v]!=-1){ 
			if(rep[u]!=-1) f[u]=gcd(f[u],abs(rep[u]-(rep[v]+ew[i])));
			else rep[u]=rep[v]+ew[i];
		} 
		pf[id]=f[u],pr[id]=rep[u];
	}
	rep[u]=-1;f[u]=0;
	if(mark[u]){
		siz[u]=1;rep[u]=0;
	}
	for(int id=e-1;id>=0;id--){
		int i=edg[u][id];
		int v=(eu[i]==u?ev[i]:eu[i]);
		f[u]=gcd(f[u],f[v]);
		if(rep[v]!=-1){ 
			if(rep[u]!=-1) f[u]=gcd(f[u],abs(rep[u]-(rep[v]+ew[i])));
			else rep[u]=rep[v]+ew[i];
		} 
		sf[id]=f[u],sr[id]=rep[u];
	}
	for(int id=0;id<e;id++){
		int i=edg[u][id],v=(eu[i]==u?ev[i]:eu[i]);
		if(v==fa) continue;
		ll _sizv=siz[v],_sizu=siz[u],_sumu=sum[u],_sumv=sum[v];
		siz[u]=_sizu-_sizv;
		sum[u]=_sumu-_sumv-ew[i]*_sizv;
		f[u]=gcd(id?pf[id-1]:0,id<e-1?sf[id+1]:0);
		if(id>0&&pr[id-1]!=-1&&id<e-1&&sr[id+1]!=-1) f[u]=gcd(f[u],abs(pr[id-1]-sr[id+1]));
		rep[u]=(id>0&&pr[id-1]!=-1?pr[id-1]:(id<e-1?sr[id+1]:-1));
		root(v,u);
		siz[v]=_sizv;siz[u]=_sizu;sum[u]=_sumu;sum[v]=_sumv;
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>k;
	if(k==1){cout<<"0"<<endl;return 0;} 
	while(k--){int u;cin>>u;mark[u]=true;} 
	for(int i=1;i<n;i++){
		cin>>eu[i]>>ev[i]>>ew[i];
		edg[eu[i]].push_back(i);
		edg[ev[i]].push_back(i);
	}
	dfs(1,0);root(1,0);
	cout<<ans*2<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 3ms
memory: 15408kb

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:

-4

result:

wrong answer 1st numbers differ - expected: '24', found: '-4'