题解：P15877 [ICPC 2026 NAC] Cable Pruning

· · 题解

题意

给你一棵基环树和一些点对，保留权值和尽可能小的边使得每个点对仍然可以互相到达。

做法

先把环抠出来，设点对是 (x,y)。

如果 x 和 y 都在环上同一个点的子树中，那么路径是唯一的，求出 LCA，树上差分一下是好做的。

否则，那么从 x 到根（环上的某个点，而非整个环）和从 y 到根的路径也都是要保留的，也可以树上差分。

而剩下的部分在环上有两种走法，找到一种策略选择哪些边留下对我来说还是太困难了，那该怎么做呢？

我们发现，你断掉任意一条边，那么每个点对就只能有一种走法了，所以枚举每条边把它断掉，用线段树可以做到 O(n\log n)。

于是你做完了这道题。

码风很丑，轻喷。

#include<bits/stdc++.h>
using namespace std;
int cnt,z[100005],zz[100005],u[100005],d[100005],dd[100005],hc,bc[100005];
int fu[100005],fd[100005],fa[100005],s[100005],e[100005],de[100005];
long long n,K,h[100005],c[100005],an,an1;
struct node{int n,d,c;}b[200005];
struct Node{int x,y;}a[100005],aa[100005];
struct tr{long long x,y,z;}t[800005];
vector<int>bb[100005],cc[100005];
void csh(int x,int y)
{
    u[x]=1;
    for(int i=h[x];i;i=b[i].n)
    {
        if(b[i].d==y)continue;
        if(u[b[i].d])
        {
            if(!hc)
            {
                while(zz[cnt]!=b[i].d&&cnt)++hc,d[hc]=z[cnt],dd[hc]=zz[cnt],--cnt;
                for(int i=1;i<=hc/2;i++)swap(d[i],d[hc-i+1]),swap(dd[i],dd[hc-i+1]);
                ++hc,d[hc]=b[i].c,dd[hc]=b[i].d;
            }
            continue;
        }
        z[++cnt]=b[i].c;
        zz[cnt]=b[i].d;
        csh(b[i].d,x);
    }
    --cnt;
}
void csh2(int x,int y)
{
    fu[x]=fu[y];
    fa[x]=y;
    de[x]=de[y]+1;
    s[x]=1;
    for(int i=h[x];i;i=b[i].n)
    {
        if(b[i].d==y||u[b[i].d])continue;
        csh2(b[i].d,x);
        s[x]+=s[b[i].d];
        if(s[b[i].d]>s[e[x]])e[x]=b[i].d;
    }
}
void csh3(int x,int y)
{
    fd[x]=y;
    if(e[x])csh3(e[x],y);
    for(int i=h[x];i;i=b[i].n)
    {
        if(b[i].d==fa[x]||b[i].d==e[x]||u[b[i].d])continue;
        csh3(b[i].d,b[i].d);
    }
}
int LCA(int x,int y)
{
    while(fd[x]!=fd[y])
    {
        if(de[fd[x]]<de[fd[y]])swap(x,y);
        x=fa[fd[x]];
    }
    return de[x]<de[y]?x:y;
}
void hi(int x,int y)
{
    for(int i=h[x];i;i=b[i].n)
    {
        if(b[i].d==fa[x]||u[b[i].d])continue;
        hi(b[i].d,b[i].c);
        bc[x]+=bc[b[i].d];
    }
    if(bc[x])an1+=c[y];
}
void bu(int x,int l,int r)
{
    if(l==r)
    {
        t[x].z=c[d[l]];
        return ;
    }
    int mid=(l+r)>>1;
    bu(x*2,l,mid);
    bu(x*2+1,mid+1,r);
    t[x].z=t[x*2].z+t[x*2+1].z;
}
void g(int x,int l,int r,int L,int R,int v)
{
    if(L<=l&&r<=R)
    {
        t[x].y+=v;
        if(t[x].y)t[x].x=t[x].z;
        else t[x].x=t[x*2].x+t[x*2+1].x;
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=L)g(x*2,l,mid,L,R,v);
    if(mid<R)g(x*2+1,mid+1,r,L,R,v);
    if(t[x].y)t[x].x=t[x].z;
    else t[x].x=t[x*2].x+t[x*2+1].x;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>K;
    for(int i=1,x,y,z;i<=n;i++)
    {
        cin>>x>>y>>z;
        c[i]=z;
        b[i]={h[x],y,i},h[x]=i;
        b[i+n]={h[y],x,i},h[y]=i+n;
    }
    csh(1,1);
    for(int i=1;i<=n;i++)u[i]=0;
    for(int i=1;i<=hc;i++)u[dd[i]]=i;
    for(int i=1;i<=hc;i++)
    {
        fu[dd[i]]=dd[i];
        csh2(dd[i],dd[i]);
        csh3(dd[i],dd[i]);
    }
    bu(1,1,hc);
    cnt=0;
    for(int i=1,x,y,lca;i<=K;i++)
    {
        cin>>x>>y;
        a[i]={x,y};
        bc[x]++,bc[y]++;
        if(fu[x]==fu[y])
        {
            lca=LCA(x,y);
            bc[lca]-=2;
        }
        else
        {
            bc[fu[x]]--,bc[fu[y]]--;
            aa[++cnt]={u[fu[x]],u[fu[y]]};
            if(aa[cnt].x>aa[cnt].y)swap(aa[cnt].x,aa[cnt].y);
            g(1,1,hc,aa[cnt].x+1,aa[cnt].y,1);
            bb[aa[cnt].x].push_back(aa[cnt].y);
            cc[aa[cnt].y].push_back(aa[cnt].x);
        }
    }
    for(int i=1;i<=hc;i++)
    {
        hi(dd[i],0);
    }
    an=t[1].x;
    for(int i=2;i<=hc;i++)
    {
        for(int j:cc[i-1])
        {
            g(1,1,hc,j+1,i-1,1);
            g(1,1,hc,i,hc,-1);
            g(1,1,hc,1,j,-1);
        }
        for(int j:bb[i-1])
        {
            g(1,1,hc,i,j,-1);
            g(1,1,hc,j+1,hc,1);
            g(1,1,hc,1,i-1,1);
        }
        an=min(an,t[1].x);
    }
    cout<<an+an1<<'\n';
    return 0;
}