题解：P12357 [eJOI 2024] 贸易搭配 / Many Pairs

· · 题解

挺恶心的分讨题。

令 fa_{x,y} 表示以 1 为根时 x 的 y 级祖先，fa_x 表示父亲。

将一对贸易关系 (A,B,C) 的贡献分为：

值得注意的是：一种选择方案有多种贡献，需要以得当的方式结合；度数小于等于 1 时可以取到所有贡献；在 (A,B) 是祖先关系时需要特殊讨论端点的取舍。

于是我们只需要求 k 级祖先与 \operatorname{lca}，加上树上差分变完成了这道题，时间复杂度 O(n \log n )。用并查集求祖先与 \operatorname{lca} ，且对于第四种贡献在外层桶排后加入 vector，可以做到 O(n \alpha(n))。

int n,m,a[N],b[N],c[N],lca[N],af[N],bf[N],f[N],lst[N];
int find(int x){
    if(f[x]==x) return x;
    int p=f[x];
    f[x]=find(f[x]);
    lst[x]=lst[p]?lst[p]:(lst[x]?lst[x]:x);
    return f[x];
}
vector<int> Q[N];
int stk[N],top,dep[N],fa[N];
void dfs(int p){
    stk[dep[p]=++top]=p;
    f[p]=p;
    for(int i:Q[p])
        if(lca[i]==-1){
            lca[i]=find(a[i]^b[i]^p);
            af[i]=stk[dep[lca[i]]+1];
            bf[i]=lst[a[i]^b[i]^p];
            if(b[i]==p) swap(af[i],bf[i]);
        }else lca[i]=-1;
    for(int o=head[p];o;o=nxt[o])
        if(to[o]^fa[p]) fa[to[o]]=p,dfs(to[o]);
    f[p]=fa[p];--top;
}
#define ll long long
struct node{int u,v,c;};
inline bool cmp(node x,node y){return x.u==y.u?x.v<y.v:x.u<y.u;}
vector<node> T[N];
ll val[N],fv[N],ffv[N],Sum,ans[N];
void solve(int p){
    ll mx=-1;
    for(int o=head[p];o;o=nxt[o]) if(to[o]^fa[p]){
        solve(to[o]);
        val[p]+=val[to[o]],fv[p]+=fv[to[o]],ffv[p]+=ffv[to[o]];
        if(~mx) ans[p]=max(ans[p],mx+val[to[o]]);
        mx=max(mx,val[to[o]]);
    }
    sort(T[p].begin(),T[p].end(),cmp);
    for(int i=0;i<T[p].size();){
        int x=T[p][i].u,y=T[p][i].v;ll res=0;
        while(i<T[p].size()&&T[p][i].u==x&&T[p][i].v==y) res+=T[p][i++].c;
        ans[p]=max(ans[p],res+val[x]+val[y]);
    }
    for(int o=head[p];o;o=nxt[o])if(to[o]^fa[p]){
        ans[p]=max(ans[p],ffv[to[o]]+val[to[o]]+Sum-fv[p]);
    }
    if(!nxt[head[p]]) ans[p]=Sum;
}
int main(){
    read(n),read(m);
    for(int i=1;i<n;++i){
        int u,v;
        read(u),read(v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=m;++i){
        read(a[i]),read(b[i]),read(c[i]);
        Q[a[i]].push_back(i);
        Q[b[i]].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=m;++i){
        //af bf 表示 A/B 的 dep[A/B] - dep[lca] -1 级祖先 
        if(af[i]&&bf[i]){
            T[lca[i]].push_back((node){min(af[i],bf[i]),max(af[i],bf[i]),c[i]});//第4种 
            val[lca[i]]+=c[i];//第1种 
            fv[fa[a[i]]]+=c[i],fv[fa[b[i]]]+=c[i],fv[lca[i]]-=c[i];//第2种 
        }else{
            val[af[i]^bf[i]]+=c[i];//第1种 
            fv[fa[lca[i]^a[i]^b[i]]]+=c[i];//第2种 
        }
        if(af[i]) ffv[a[i]]+=c[i],ffv[af[i]]-=c[i];
        if(bf[i]) ffv[b[i]]+=c[i],ffv[bf[i]]-=c[i];//第3种 
        Sum+=c[i];
    }
    solve(1);
}