QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106395#5313. Please Save PigelandqinsanmaRE 7ms42176kbC++145.4kb2023-05-17 17:16:092023-05-17 17:16:13

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-17 17:16:13]
  • 评测
  • 测评结果:RE
  • 用时:7ms
  • 内存:42176kb
  • [2023-05-17 17:16:09]
  • 提交

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

output:


result: