QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#232438#5313. Please Save PigelandAlishRE 5ms20088kbC++173.4kb2023-10-30 14:17:092023-10-30 14:17:09

Judging History

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

  • [2023-10-30 14:17:09]
  • 评测
  • 测评结果:RE
  • 用时:5ms
  • 内存:20088kb
  • [2023-10-30 14:17:09]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

ll mod = 1e9+7 ;


const int N = 5e5+23;
const ll INF=LLONG_MAX;
vector<pll> g[N];
ll distu[N], distd[N], sz[N], is[N];
pll dpd[N], dpu[N]; // for GCD
int n, k;


void dfs(int v, int p=0){
    for (auto pp: g[v]){
        int u=pp.F;
        ll w=pp.S;
        if(u==p )continue;
        dfs(u, v);
        distd[v]+=w*sz[u]+distd[u];
        sz[v]+=sz[u];
        pll temp= dpd[u];
        if(temp.F || is[u])temp.F+=w;
        if(dpd[v].F==0 && dpd[v].S==0 && !is[v]) {dpd[v]=temp; continue;}
        if(temp.F< dpd[v].F ) swap(temp, dpd[v]);
        dpd[v].S=__gcd(__gcd(dpd[v].S, temp.S), temp.F-dpd[v].F);
    }

}

void DFS(int v, int p=0){

    pll pref[g[v].size()+23], suff[g[v].size()+23];
    pref[0]=dpu[v]; suff[g[v].size()-1]=dpu[v];

    for (int i=0; i<g[v].size(); i++){
        int u=g[v][i].F;
        ll w=g[v][i].S;
        if(u==p) {pref[i+1]=pref[i]; continue; }
        pll r1=pref[i];
        pll r2=dpd[u];
        if(r2.F|| is[u])r2.F+=w;
        if(r1.F>r2.F) swap(r1, r2);
        if(r1.F==0 && r1.S==0){
            pref[i+1]=r2;
            continue;
        }
        pref[i+1].F=r1.F;
        pref[i+1].S=__gcd(__gcd(r1.S, r2.S), r2.F-r1.F);
    }
    for (int i=g[v].size()-1; i>0; i--){
        int u=g[v][i].F;
        ll w=g[v][i].S;
        if(u==p) {suff[i-1]=suff[i]; continue; }
        pll r1=suff[i];
        pll r2=dpd[u];
        if(r2.F || is[u])r2.F+=w;
        if(r1.F>r2.F) swap(r1, r2);
        if(r1.F==0 && r1.S==0){
            suff[i-1]=r2;
            continue;
        }
        suff[i-1].F=r1.F;
        suff[i-1].S=__gcd(__gcd(r1.S, r2.S), r2.F-r1.F);
    }

    for (int i=0; i<g[v].size(); i++){
        int u=g[v][i].F;
        ll w=g[v][i].S;
        if(u==p) continue;
        pll r1=pref[i];
        pll r2=suff[i];

        if(r1.F || is[v]) r1.F+=w;
        if(r2.F || is[v]) r2.F+=w;

        if(r1.F>r2.F) swap(r1, r2);
        if(is[u]){
            dpu[u].F=0;
            dpu[u].S=__gcd(__gcd(r1.F, r1.S), __gcd(r2.F, r2.S));
        }
        else if(r1.F==0 && r1.S==0) dpu[u]=r2;
        else{
            dpu[u].F=r1.F;
            dpu[u].S=__gcd(__gcd(r1.S, r2.S), r2.F-r1.F);
        }
        distu[u]=distu[v]+distd[v]-distd[u]+(k-sz[u])*w- w*sz[u];
        DFS(u, v);
    }
}

int main()
{

    cin>>n>>k;
    for (int i=0; i<k; i++){int v; cin>>v; sz[v]++; is[v]++;}

    for (int i=0; i<n-1; i++){
        int u, v; cin>>v>>u;
        ll w; cin>>w;
        g[v].pb({u, w}); g[u].pb({v, w});
    }
    dfs(1);
    DFS(1);
    ll ans=INF;
    for (int v=1; v<=n; v++){
        ans=min( ans, (distd[v]+distu[v])/__gcd(__gcd(dpd[v].F, dpd[v].S), __gcd(dpu[v].F, dpu[v].S)));
        //cout<<__gcd(__gcd(dpd[v].F, dpd[v].S), __gcd(dpu[v].F, dpu[v].S))<<" "<<distd[v]+distu[v]<<endl;
    }
    cout<<ans*2<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 19900kb

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: 0
Accepted
time: 0ms
memory: 20088kb

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:

24

result:

ok 1 number(s): "24"

Test #3:

score: -100
Runtime Error

input:

1 1
1

output:


result: