QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#698893 | #5313. Please Save Pigeland | frogman | RE | 0ms | 24616kb | C++14 | 1.6kb | 2024-11-01 22:56:32 | 2024-11-01 22:56:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 500010
#define int long long
int sz[N],L[N],R[N],w[N],book[N],a[N],t[N<<2];
vector<pair<int,int> > g[N];
int n,k,sum,ans=1e18;
void build(int l,int r,int now){
if(l==r){
t[now]=a[l];
return;
}
int mid=l+r>>1;
build(l,mid,now<<1);
build(mid+1,r,now<<1|1);
t[now]=__gcd(t[now<<1],t[now<<1|1]);
}
void upt(int l,int r,int x,int y,int now){
if(x<1||x>k){
return;
}
if(l==r){
t[now]+=y;
return;
}
int mid=l+r>>1;
if(x<=mid){
upt(l,mid,x,y,now<<1);
}else{
upt(mid+1,r,x,y,now<<1|1);
}
t[now]=__gcd(t[now<<1],t[now<<1|1]);
}
void dfs(int x,int fa){
if(book[x]){
sum+=w[x];
L[x]=++L[0];
a[L[0]]=w[x];
}
for(auto b: g[x]){
int v=b.first;
int c=b.second;
if(v==fa){
continue;
}
w[v]=w[x]+c;
dfs(v,x);
L[x]=min(L[x],L[v]);
}
R[x]=L[0];
}
void Dfs(int x,int fa,int s){
ans=min(ans,s/abs(t[1]));
for(auto b: g[x]){
int v=b.first;
int c=b.second;
if(v==fa){
continue;
}
upt(1,k,1,c,1);
upt(1,k,L[v],-c-c,1);
upt(1,k,R[v]+1,c+c,1);
Dfs(v,x,s+(k-2*(R[v]-L[v]+1))*c);
upt(1,k,1,-c,1);
upt(1,k,L[v],+c+c,1);
upt(1,k,R[v]+1,-c-c,1);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=k;++i){
int x;
cin>>x;
book[x]=1;
}
for(int i=1;i<n;++i){
int x,y,z;
cin>>x>>y>>z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
for(int i=1;i<=n;++i){
L[i]=1e9;
}
dfs(1,0);
for(int i=L[0];i;--i){
a[i]-=a[i-1];
}
build(1,k,1);
Dfs(1,0,sum);
cout<<ans*2;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 24616kb
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: 15392kb
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