题解：P15877 [ICPC 2026 NAC] Cable Pruning

cheng2010 · 2026-10-20 16:10:30 · 题解

来一个线性做法。

首先考虑子树内怎么做，显然路径上的点是一定要保留的，那么怎么判断一条边是否要保留？显然可以路径加，可以树上差分维护，但是这样太劣了，考虑更优，两个点异或上一个随机权值，那么就变成了子树异或，这样是 O(n) 的。

到了环上，注意到如果一段区间内异或和为 0，那么可以直接将这段区间的两端断开来，一定是可以的。

记子树的答案为 s，环长为 l。

维护前缀子树异或和，记 F(x) 表示异或和为 x 的边权和（边是连到环的下一个的边）那么答案就是：s+l-\max F(x)。

总复杂度 O(n)。

:::success[code]

#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
using namespace std;
const int N=1e5+7;
int n,m;
vector<pair<int,int>>edge[N];
int st[N],top;
int vis[N];
vector<int>clr;
inline void dfs(int x,int lst)
{
    if(clr.size())return;
    if(vis[x])
    {
        for(int i=top;i;i--)
        {
            clr.push_back(st[i]);
            if(st[i]==x)break;
        }
        return;
    }
    vis[x]=1;
    st[++top]=x;
    for(auto [v,w]:edge[x])
    {
        if(v==lst)continue;
        dfs(v,x);
        if(clr.size())return;
    }
    top--;
}
int fa[N];
inline void dfs1(int x,int rt)
{
    vis[x]=rt;
    for(auto [v,w]:edge[x])
    {
        if(vis[v]!=0||v==fa[x])continue;
        fa[v]=x;
        dfs1(v,rt);
    }
}
mt19937_64 rnd(time(0));
ull sum[N];
int ans;
inline void dfs2(int x,int rt)
{
    for(auto [v,w]:edge[x])
    {
        if(vis[v]!=rt||v==fa[x])continue;
        dfs2(v,rt);
        sum[x]^=sum[v];
    }
}
inline void dfs3(int x,int rt)
{
    for(auto [v,w]:edge[x])
    {
        if(vis[v]!=rt||v==fa[x])continue;
        if(sum[v])ans+=w;
        dfs3(v,rt);
    }
}
int a[N],b[N];
unordered_map<ull,int>mp;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,x,y,w;i<=n;i++)
    {
        cin>>x>>y>>w;
        edge[x].push_back({y,w});
        edge[y].push_back({x,w});
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)vis[i]=0;
    for(int v:clr)vis[v]=1;
    for(int v:clr)dfs1(v,v);
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
        ull w=rnd();
        sum[a[i]]^=w;
        sum[b[i]]^=w;
    }
    for(int v:clr)dfs2(v,v);
    for(int v:clr)dfs3(v,v);
    for(int i=1;i<=m;i++)
        a[i]=vis[a[i]],b[i]=vis[b[i]];
    int s=clr.size();
    int tot=0,mx=0;
    ull cur=0;
    for(int i=0;i<s;i++)
    {
        int x=clr[i],y=clr[(i+1)%s];
        int w=0;
        for(auto [v,c]:edge[x])
        {
            if(v==y)
            {
                w=c;
                break;
            }
        }
        tot+=w;
        cur^=sum[x];
        mp[cur]+=w;
    }
    for(auto it=mp.begin();it!=mp.end();it++)
        mx=max(mx,it->second);
    cout<<ans+tot-mx<<'\n';
}

:::