QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#279717#5313. Please Save PigelandkoalaTL 3ms19772kbC++142.7kb2023-12-08 23:57:212023-12-08 23:57:22

Judging History

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

  • [2023-12-08 23:57:22]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:19772kb
  • [2023-12-08 23:57:21]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: