QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106395 | #5313. Please Save Pigeland | qinsanma | RE | 7ms | 42176kb | C++14 | 5.4kb | 2023-05-17 17:16:09 | 2023-05-17 17:16:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll gcdd[500000*4+10];
int dfn[500000*4+10],bookc[500000*4+10];
vector<pair<int,ll>>v[500000+10];
ll dissum[500000+10],dis[500000+10],cnt[500000+10];
int c[500000+10],timecnt;
ll dp[500000+10];
ll b[500000+10],a[500000+10];
int minn[5000000+10],maxx[500000+10],m,minnid[500000+10],maxxid[500000+10];
void build(int root,int l,int r)
{
if(l==r)
{
gcdd[root]=b[l];
return ;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
gcdd[root]=__gcd(gcdd[root<<1],gcdd[root<<1|1]);
}
void change(int root,int l,int r,int pos,int val)
{
if(l==r)
{
gcdd[root]+=val;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid)
change(root<<1,l,mid,pos,val);
else
change(root<<1|1,mid+1,r,pos,val);
gcdd[root]=__gcd(gcdd[root<<1],gcdd[root<<1|1]);
}
int getgcd(int root,int l,int r,int pos)
{
if(l==r)
{
return gcdd[root];
}
int mid=(l+r)>>1;
if(pos<=mid)
return getgcd(root<<1,l,mid,pos);
else
return getgcd(root<<1|1,mid+1,r,pos);
}
void dfs1(int now,int pre)
{
timecnt++;
dfn[now]=timecnt;
cnt[now]=bookc[now];
minn[now]=1e9;
maxx[now]=0;
if(bookc[now])
{
minn[now]=dfn[now];
maxx[now]=dfn[now];
}
for(auto it:v[now])
{
if(it.first==pre)
continue;
dis[it.first]=dis[now]+it.second;
dfs1(it.first,now);
dissum[now]+=(dissum[it.first]+cnt[it.first]*it.second);
cnt[now]+=cnt[it.first];
}
}
void dfs2(int now,int pre,ll val)
{
if(now!=1)
{
ll tempsum=dp[pre]-dp[now];
ll tempcnt=cnt[now]*val;
tempsum-=tempcnt;
ll fuckcnt=cnt[pre]-cnt[now];
fuckcnt*=val;
dp[now]+=tempsum+fuckcnt;
cnt[now]=cnt[pre];
}
for(auto it:v[now])
{
if(it.first==pre)
continue;
dfs2(it.first,now,it.second);
}
}
bool cmp(int x,int y)
{
return dfn[c[x]]<dfn[c[y]];
}
int AL,AR;
ll gcdnow[500000+10];
void work(int now,int pre,ll val)
{
if(now!=1&&minn[now]!=1e9)
{
//完全修改
// cout<<"修改" <<now<<" "<<minnid[now]<<" "<<maxxid[now]<<" "<<val<<endl;
change(1,1,m,minnid[now],-val);
if(maxxid[now]+1<=m)
change(1,1,m,maxxid[now]+1,val);
if(minnid[now]!=1)
{
change(1,1,m,AL,val);
change(1,1,m,minnid[now],-val);
}
if(maxxid[now]+1<=m)
change(1,1,m,maxxid[now]+1,val);
gcdnow[now]=gcdd[1];
/*
for(int i=1;i<=m;i++)
{
cout<<getgcd(1,1,m,i)<<" ";
}
cout<<endl;
*/
}
for(auto it:v[now])
{
if(it.first==pre)
continue;
work(it.first,now,it.second);
}
}
int pos[500000+10];
void dfs(int now,int pre)
{
maxx[now]=0;
minn[now]=1e9;
if(bookc[now])
{
maxx[now]=dfn[now];
minn[now]=dfn[now];
maxxid[now]=pos[dfn[now]];
minnid[now]=pos[dfn[now]];
}
for(auto it:v[now])
{
if(it.first==pre)
continue;
dfs(it.first,now);
if(maxx[now]<maxx[it.first])
{
maxx[now]=maxx[it.first];
maxxid[now]=maxxid[it.first];
}
if(minn[now]>minn[it.first])
{
minn[now]=minn[it.first];
minnid[now]=minnid[it.first];
}
}
}
int main()
{
/*
gcd(a,b,c)
gcd(a,gcd(b,c-b))
gcd(gcd(a,b-a) ,c-b)
gcd(a,b,c)等于
gcd(a,b-a,c-b)差分数组
区间修改时[L,R]
端点[L]+=
端点[R+1]-=即可
*/
int n;
cin>>n>>m;
if(m==1)
{
cout<<0;
return 0;
}
for(int i=1; i<=m; i++)
{
cin>>c[i];
bookc[c[i]]=1;
}
for(int i=1; i<n; i++)
{
int x,y;
ll z;
cin>>x>>y>>z;
v[x].push_back(make_pair(y,z));
v[y].push_back(make_pair(x,z));
}
dfs1(1,0);
dp[1]=dissum[1];
/*
for(int i=1;i<=n;i++)
{
cout<<dissum[i]<<" ";
}
cout<<endl;*/
dfs2(1,0,0);
/*
for(int i=1;i<=n;i++)
{
cout<<dp[i]<<" ";
}
*/
for(int i=1;i<=m;i++)
{
a[i]=i;
}
sort(a+1,a+1+m,cmp);
// cout<<endl;
for(int i=1;i<=m;i++)
{
// cout<<c[a[i]]<<" ";
b[i]=dis[c[a[i]]]-dis[c[a[i-1]]];
pos[dfn[c[a[i]]]]=i;
//cout<<b[i]<<" ";
}
// cout<<endl;
// cout<<"pos"<<endl;
/*
for(int i=1;i<=n;i++)
{
cout<<pos[i]<<" ";
}
cout<<endl;*/
dfs(1,0);
/*
for(int i=1;i<=n;i++)
{
cout<<minnid[i]<<" "<<maxxid[i]<<endl;
}*/
AL=1;
AR=m;
build(1,1,m);
/*
cout<<getgcd(1,1,m,1)<<endl;
cout<<"here"<<endl;*/
/* for(int i=1;i<=m;i++)
{
cout<<getgcd(1,1,m,i)<<" ";
}
cout<<endl;
cout<<endl;*/
gcdnow[1]=gcdd[1];
/*
cout<<"gcd"<<" "<<gcd[1]<<endl;*/
work(1,0,0);
ll ans=1e18;
for(int i=1;i<=n;i++)
{
// cout<<gcdnow[i]<<" ";
ans=min(ans,2ll*dp[i]/abs(gcdnow[i]));
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 42176kb
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
Runtime Error
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