QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235878 | #5313. Please Save Pigeland | ushg8877# | WA | 3ms | 23292kb | C++20 | 2.8kb | 2023-11-03 11:49:31 | 2023-11-03 11:49:32 |
Judging History
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'