2022icpc杭州M——线段树+换根

Posted on 2023-01-07 Edited on 2023-01-08 In 数据结构

题面好长，看了好久的。其实要求的东西很简单，看懂题之后秒出思路了。

由于我以前封装过《区间加，维护区间gcd》的板子，所以直接贴一波板子，然后写+调只花了40min，然而喜提Tle on test 22。此后就是漫长的卡常，无果，期间一度怀疑是出题人特意卡掉了这种复杂度。然后突然想起cf上好像scanf巨慢，于是换成关同步流cin就过了。。。总共花了1h

现在看之前封装的《区间加，维护区间gcd》依托答辩！（不过正确性还是有保证的）打算近期重新封装下。

先贴个代码在这：（好像确实有不用线段树复杂度更优的做法，之后再看）

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

struct ADD_GCD//要求支持：a数组区间加，查询区间gcd
{    
    const int n;
    const vector<ll>a;//原数组a是差分数组d的前缀和 
    
    vector<ll>d;//差分数组时刻保持正确 
    
    ADD_GCD(const vector<ll> &init) : n(init.size()-1) , a(init)
    {
        assert(a[0]==0);
        d.resize(n+1) , d[0]=0;
        for(int i=1;i<=n;++i)d[i]=a[i]-a[i-1];
        
        function<void(int,int,int)>build = [&](int rt,int l,int r)
        {
            if(l==r)return info[rt]={d[l]} , void();
            
            int mid=l+r>>1;
            build(rt<<1,l,mid) , build(rt<<1|1,mid+1,r);
            gengxin(rt);
        };
        info.resize(4<<__lg(n)) , build(1,1,n);
        
        BIT.resize(n+1) , BIT[0]=0;
        for(int i=1;i<=n;++i)BIT[i]=a[i]-a[i-lowbit(i)];
    }
    
    
    struct INFO
    {
        ll g;
        INFO operator+(const INFO &a)const
        {
            return {__gcd(g,a.g)};
        }
    };
    static constexpr INFO E={0};//单位元 
    vector<INFO>info;//线段树维护差分数组d（单点赋值，查询区间gcd） 
    void gengxin(int rt)
    {
        info[rt]=info[rt<<1]+info[rt<<1|1];
    }
    
    void ddxg(int rt,int l,int r,int x,const INFO &C)
    {
        if(l==r)return info[rt]=C , void();
        
        int mid=l+r>>1;
        if(x<=mid)ddxg(rt<<1,l,mid,x,C);
        else ddxg(rt<<1|1,mid+1,r,x,C);
        gengxin(rt);
    }
    void ddxg(int x,ll C)//d[x]=C 
    {
        assert(d[x]==C) , ddxg(1,1,n,x,{d[x]});
    }
    
    INFO chaxun(int rt,int l,int r,int L,int R)
    {
        if(L<=l && r<=R)return info[rt];
        INFO res=E;  int mid=l+r>>1;
        if(L<=mid)res=res+chaxun(rt<<1,l,mid,L,R);
        if(R>mid)res=res+chaxun(rt<<1|1,mid+1,r,L,R);
        return res;
    }
    ll chaxun(int L,int R)//gcd(d[L],...,d[R])
    {
        return chaxun(1,1,n,L,R).g; 
    }
    
    
    inline int lowbit(int x){return x&-x;}
    vector<ll>BIT;//BIT维护差分数组d 
    void xg(int l,int r,ll del)//原数组a区间加，a[l~r]+=del
    {
        int x=l;
        d[x]+=del , ddxg(x,d[x]);
        while(x<=n)BIT[x]+=del , x+=lowbit(x);
        
        x=r+1;if(x>n)return;
        d[x]-=del , ddxg(x,d[x]);
        while(x<=n)BIT[x]-=del , x+=lowbit(x);
    }
    ll cx(int x)//查询原数组a的单点值a[x]
    {
        ll res=0;
        while(x)res+=BIT[x] , x-=lowbit(x);
        return res;
    }
    
    
    void op1(int l,int r,ll del)
    {
        xg(l,r,del);
    }
    ll op2(int l,int r)
    {
        //return assert(l==1 && r==n) , abs(chaxun(1,n));
        //这题只会查全部的gcd，卡常一下 
        
        ll al=cx(l) , res;
        
        if(l==r)res=al;
        else res=__gcd(al,chaxun(l+1,r));
        
        return abs(res);//abs很关键，保证gcd非负！ 
    }
};


constexpr int N=5e5+5;
struct E{int to,nex;ll w;}e[N<<1];
int head[N],tot;
void ae(int u,int v,ll w)
{
    ++tot , e[tot]={v,head[u],w} , head[u]=tot;
}

bool isu[N];
struct subtree_dfn
{
    int mn,mx;
    void merge(const subtree_dfn &a) 
    {
        if(a.mn==-1)return assert(a.mx==-1) , void();
        else 
        {
            if(mn==-1)
            {
                assert(mx==-1);
                mn=a.mn , mx=a.mx;
            }
            else
            {
                assert(mx!=-1);
                mn=min(mn,a.mn) , mx=max(mx,a.mx);
            }
            
            assert(mn!=-1 && mx!=-1);
        }
    }
}dfn[N];
int dfn_table[N],js_dfn;
ll shen[N];
void get_dfn(int u,int fa)//只有关键点才++dfn 
{
    if(isu[u])
    {
        ++js_dfn;
        dfn[u]={js_dfn,js_dfn};
        dfn_table[js_dfn]=u;
    }
    else dfn[u]={-1,-1};
    
    for(int i=head[u];i;i=e[i].nex)
    {
        int v=e[i].to;
        if(v==fa)continue;
        
        shen[v]=shen[u]+e[i].w , get_dfn(v,u);
        dfn[u].merge(dfn[v]);
    }
}

ll smdis,ans=1e18;
struct OP
{
    int l,r;
    ll del;
    
    bool ok(){return l<=r;}
    void cao(ADD_GCD &QJ,int op=1)
    {
        if(op>0)QJ.op1(l,r,del);
        else QJ.op1(l,r,-del);
    }
};
void dfs(int u,int fa,ADD_GCD &QJ)
{
    ll g=QJ.op2(1,QJ.n);
    assert(smdis%g==0);
    ans=min(ans,smdis/g);
    
    for(int i=head[u];i;i=e[i].nex)
    {
        int v=e[i].to;
        if(v==fa)continue;
        
        int qi=dfn[v].mn , mo=dfn[v].mx;
        int jsv = (qi==-1) ? 0 : mo-qi+1;
        int outv = QJ.n-jsv;
        
        ll del=e[i].w*(outv-jsv);
        smdis+=del;
        
        stack<OP>stk;
        if(jsv==0)
        {
            OP op={1,QJ.n,+e[i].w};
            assert(op.ok());
            op.cao(QJ,1) , stk.push(op);
        }
        else
        {
            OP op={qi,mo,-e[i].w};
            assert(op.ok());
            op.cao(QJ,1) , stk.push(op);
            
            op={1,qi-1,+e[i].w};
            if(op.ok())op.cao(QJ,1) , stk.push(op);
            
            op={mo+1,QJ.n,+e[i].w};
            if(op.ok())op.cao(QJ,1) , stk.push(op);
        }
        
        dfs(v,u,QJ);
        
        while(!stk.empty())
        {
            OP op=stk.top();stk.pop();
            op.cao(QJ,-1);
        }
        smdis-=del;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    int n,k;cin>>n>>k;
    if(k==1)
    {
        cout<<"0\n";return 0;
    }
    
    for(int i=1;i<=k;++i)
    {
        int u;cin>>u;
        isu[u]=true;
    }
    for(int i=1;i<n;++i)
    {
        int u,v;ll w;
        cin>>u>>v>>w;
        ae(u,v,w) , ae(v,u,w);
    }
    js_dfn=0 , shen[1]=0 , get_dfn(1,0);
    smdis=0;
    for(int u=1;u<=n;++u)
    {
        if(isu[u])smdis+=shen[u];
    }
    
    vector<ll>a(k+1,0);//注意，是维护到k个点距离的gcd 
    assert(js_dfn==k);
    for(int i=1;i<=k;++i)//枚举dfn，dfn是连续的，所以能维护 
    {
        int u=dfn_table[i];
        a[i]=shen[u];
    }
    ADD_GCD QJ(a);
    
    dfs(1,0,QJ);
    cout<<2*ans<<"\n";
    return 0;
}