QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561396 | #5313. Please Save Pigeland | hhdhh | RE | 0ms | 34440kb | C++23 | 3.8kb | 2024-09-12 22:11:07 | 2024-09-12 22:11:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, a, b) for(LL i = (a); i <= (b); i++)
#define per(i, a, b) for(LL i = (a); i >= (b); i--)
#define rept(i, a, ne) for(LL i = (a); ~i ; i=ne[i])
#define debug(x) cout<<#x<<": "<<x<<endl
#define fi first
#define sec second
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef vector<LL> VI;
typedef pair<LL,LL>PII;
const LL N=1e6+10,M=2*N;
#define lc u<<1
#define rc u<<1|1
LL rk[N];
LL b[N];
struct Tree
{ //线段树
LL l,r;
LL sum,d;
}tr[N*4];
void pushup(LL u)
{ //上传
tr[u].sum=tr[lc].sum+tr[rc].sum;
tr[u].d=__gcd(tr[lc].d,tr[rc].d);
}
void init(LL u,LL l,LL r)
{ //建树
tr[u]={l,r,b[l],b[l]};
if(l==r) return;
LL m=l+r>>1;
init(lc,l,m);
init(rc,m+1,r);
pushup(u);
}
void change(LL u,LL x,LL k)
{ //点修
if(x==tr[u].l&&tr[u].r==x)
{
tr[u].sum+=k;
tr[u].d+=k;
return;
}
LL m=tr[u].l+tr[u].r>>1;
if(x<=m) change(lc,x,k);
if(x>m) change(rc,x,k);
pushup(u);
}
LL queryG(LL u,LL l,LL r)
{ //区查
if(l<=tr[u].l && tr[u].r<=r) return tr[u].d;
LL m=tr[u].l+tr[u].r>>1;
if(l<=m&&r>m)
return __gcd(queryG(lc,l,r),queryG(rc,l,r));
else if(l<=m)
return queryG(lc,l,r);
else
return queryG(rc,l,r);
}
LL querys(LL u,LL l,LL r)
{ //区查
if(l<=tr[u].l && tr[u].r<=r) return tr[u].sum;
LL m=tr[u].l+tr[u].r>>1;
LL sum=0;
if(l<=m) sum+=querys(lc,l,r);
if(r>m) sum+=querys(rc,l,r);
return sum;
}
LL h[N],ne[M],w[M],e[M],idx;
LL dfn[N],num;
LL sz[N];
LL l[N],r[N];
LL d[N];
bool bo[N];
void add(LL x,LL y,LL z)
{
w[idx]=z,e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void dfs(LL x,LL fa)
{
if(bo[x])
{
dfn[x]=++num;
sz[x]=1;
rk[num]=x;
l[x]=r[x]=num;
}
rept(i,h[x],ne)
{
LL y=e[i];
if(y==fa)continue;
d[y]=w[i]+d[x];
dfs(y,x);
sz[x]+=sz[y];
l[x]=min(l[x],l[y]);
r[x]=max(r[x],r[y]);
}
}
LL mi;
LL getgcd(LL x,LL y)
{
LL sum=querys(1,1,x);
LL d=0;
if(x<y)
d=queryG(1,x+1,y);
return abs(__gcd(sum,d));//因为如果查一个点会直接返回d(有可能是负数)
}
void dfs2(LL x,LL fa,LL sum)
{
mi=min(sum/getgcd(1,num),mi);
rept(i,h[x],ne)
{
LL y=e[i];
if(y==fa)continue;
LL psum=sum+(num-2*sz[y])*w[i];
//修改
if(l[y]>r[y])
change(1,1,w[i]);
else
{
change(1,1,w[i]);
change(1,l[y],-w[i]*2);
if(r[y]<num)
change(1,r[y]+1,w[i]*2);
}
dfs2(y,x,psum);
//还原
if(l[y]>r[y])
change(1,1,-w[i]);
else
{
change(1,1,-w[i]);
change(1,l[y],w[i]*2);
if(r[y]<num)
change(1,r[y]+1,-w[i]*2);
}
}
}
void slove()
{
memset(h,-1,sizeof h);
memset(l,0x3f,sizeof l);
mi=LLONG_MAX;
LL n,m;
cin>>n>>m;
rep(i,1,m)
{
LL x;
cin>>x;
bo[x]=1;
}
if(n==1)
{
cout<<0<<endl;
return;
}
rep(i,1,n-1)
{
LL x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
dfs(1,0);
LL sum=0;
rep(i,1,num)
{
b[i]=d[rk[i]]-d[rk[i-1]];
sum+=d[rk[i]];
}
init(1,1,num);
dfs2(1,0,sum);
cout<<mi*2<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// cout << fixed << setprecision(9);
LL t=1;
// cin>>t;
while(t--)
{
slove();
}
return 0;
}
//#pragma GCC optimize(2)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 34312kb
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: 34440kb
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: 0
Accepted
time: 0ms
memory: 21984kb
input:
1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Runtime Error
input:
100000 1 79187 72704 72659 15 32741 43496 10 21580 97447 17 55758 36700 21 32116 3643 14 60460 58764 12 75894 50624 7 58295 49393 22 43733 17210 1 58093 68769 15 1086 58916 17 25632 37710 11 49555 92976 8 32547 27060 18 84896 12811 1 3196 1242 16 18870 78236 14 2414 7945 12 48745 15399 1 17648 83791...