QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#561393#5313. Please Save PigelandhhdhhRE 2ms26224kbC++233.8kb2024-09-12 22:10:122024-09-12 22:10:12

Judging History

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

  • [2024-09-12 22:10:12]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:26224kb
  • [2024-09-12 22:10:12]
  • 提交

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=5e5+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)

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 26224kb

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: 26092kb

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: 13948kb

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...

output:


result: