QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#279717 | #5313. Please Save Pigeland | koala | TL | 3ms | 19772kb | C++14 | 2.7kb | 2023-12-08 23:57:21 | 2023-12-08 23:57:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
ll x;cin>>x;
return x;
}
ll lowbit(ll x)
{
return x&(-x);
}
const ll N=5e5+10;
ll n,k,a[N],c[N*4],gcd[N*4];
ll head[N],tot,L[N],R[N],vis[N],D[N],cnt[N],f[N];
ll SUM[N];
struct edge
{
ll y,v,next;
}e[1000010];
void add0(ll l,ll r,ll v)
{
while(l<=n)
{
c[l]+=v;
l+=lowbit(l);
}
r++;
while(r<=n)
{
c[r]-=v;
r+=lowbit(r);
}
}
ll ask0(ll x)
{
ll t=0;
while(x)
{
t=t+c[x];
x=x-lowbit(x);
}
return t;
}
void add(ll x,ll l,ll r,ll d,ll v)
{
if(l==r)
{
gcd[x]=gcd[x]+v;
return ;
}
ll mid=(l+r)/2;
if(d<=mid)
add(x*2,l,mid,d,v);
else
add(x*2+1,mid+1,r,d,v);
gcd[x]=__gcd(gcd[x*2],gcd[x*2+1]);
}
void e_add(ll x,ll y,ll v)
{
tot++;
e[tot]={y,v,head[x]};
head[x]=tot;
}
void dfs(ll x,ll fa,ll d)
{
if(vis[x])
{
tot++;
L[x]=R[x]=tot;
a[tot]=d;
cnt[x]=1;
}
else
L[x]=1e9,R[x]=-1;
for(ll i=head[x];i;i=e[i].next)
{
if(e[i].y==fa)
continue;
dfs(e[i].y,x,d+e[i].v);
L[x]=min(L[x],L[e[i].y]);
R[x]=max(R[x],R[e[i].y]);
cnt[x]+=cnt[e[i].y];
f[x]=f[x]+f[e[i].y]+e[i].v*cnt[e[i].y];
}
}
void ADD(ll l,ll r,ll v)
{
if(l>k||r<1)
return ;
add0(l,r,v);
if(l!=1)
add(1,2,k,l,v);
if(r!=k)
add(1,2,k,r+1,-v);
}
void dfs1(ll x,ll fa)
{
D[x]=abs(__gcd(gcd[1],ask0(1)));
for(ll i=head[x];i;i=e[i].next)
{
if(e[i].y==fa)
continue;
ADD(1,L[i]-1,e[i].v);
ADD(R[i]+1,k,e[i].v);
ADD(L[i],R[i],-e[i].v);
dfs1(e[i].y,x);
ADD(1,L[i]-1,-e[i].v);
ADD(R[i]+1,k,-e[i].v);
ADD(L[i],R[i],e[i].v);
}
}
void dfs2(ll x,ll fa,ll sum)
{
SUM[x]=sum+f[x];
for(ll i=head[x];i;i=e[i].next)
{
if(e[i].y==fa)
continue;
f[x]=f[x]-f[e[i].y]-e[i].v*cnt[e[i].y];
dfs2(e[i].y,x,sum+f[x]+(k-cnt[e[i].y])*e[i].v);
f[x]=f[x]+f[e[i].y]+e[i].v*cnt[e[i].y];
}
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("2.out","w",stdout);
ios::sync_with_stdio(false);
n=read();k=read();
if(k==1)
{
cout<<"0\n";
return 0;
}
if(k==2)
{
cout<<"1\n";
return 0;
}
for(ll i=1;i<=k;i++)
vis[read()]=1;
for(ll i=1;i<n;i++)
{
ll x=read(),y=read(),v=read();
e_add(x,y,v);
e_add(y,x,v);
}
tot=0;
dfs(1,0,0);
for(ll i=1;i<=k;i++)
{
add0(i,i,a[i]);
if(i!=1)
add(1,2,k,i,a[i]);
if(i!=k)
add(1,2,k,i+1,-a[i]);
}
dfs1(1,0);
dfs2(1,0,0);
ll ans=SUM[1]*2/D[1];
for(ll i=1;i<=n;i++)
ans=min(ans,SUM[i]*2/D[i]);
cout<<ans;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 19772kb
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
Time Limit Exceeded
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