题解：P10731 [NOISG 2023 Qualification] Network

sxzJOKER · 2025-03-22 22:47:50 · 题解

P10731 [NOISG 2023 Qualification] Network

LCA+树链剖分+线段树

前言

这是一道比较综合的树上题目，大概难度应该在绿到蓝左右。题面在翻译时出现了一些问题，感谢@lottle1212__指出的题面与数据注意事项。

分析

通过样例可以发现，题面中

“第 j 个应用程序如果对下面两个条件中的一个条件成立时，可以运行：”

翻译有误，实际含义应为：

“第 j 个应用程序如果对下面两个条件都成立时，可以运行：”

因此题面可理解为： 一颗 n 个结点的树，给出 m 对结点，要求求出元素数最小的点集 V，使得每一对结点之间的路径（包括头尾）上，都至少有一个结点在该点集中。

那么我们有初步的想法，使用贪心，统计所有询问的路径经过的点的频率，删除频率最高的点，再考虑没有因此断开的路径，如此重复直到所有路径都被破坏。（然鹅超时了）

注意到，在一条路径中，切断深度最浅的结点可能破坏的路径数最大。即，可以计算每一条路径上深度最浅的结点进行贪心，可以通过 LCA 算法计算。

对于每条询问路径是否已经被切断，使用线段树进行区间的快速统计。最后使用树链剖分更快的处理每一条路径所经过的结点。

最终的时间复杂度应为 O(n + m \log{n})。

实现

线段树功能：

• build：初始化线段树
• update：将某个节点标记为停机
• check：查询路径上是否存在停机节点（区间最大值查询）。

树链剖分：

第一次 DFS (dfs1)：

• 计算每个节点的父节点(f[u])、深度(d[u])、子树大小(sz[u])、重儿子(sn[u]）。
• 重儿子：子树大小最大的子节点，用于链分解。

第二次 DFS (dfs2)：

• 为每个节点分配时间戳(dfn[u])，并标记其所在链的顶部(tp[u]）。
• 重链优先遍历，确保每条链的节点在 DFS 序中连续。

贪心逻辑

计算每条路径的 LCA：

对每个应用程序的路径(a[i],b[i])，计算其 LCA 节点 lc。

按 LCA 深度排序：

将应用程序按 LCA 的深度从大到小排序。深度大的 LCA 更靠近叶子，优先处理可以覆盖更多子路径。

依次处理应用程序：

对每个应用程序，检查其路径上是否已有停机节点（通过线段树查询）。

如果没有停机节点，选择其 LCA 作为停机节点，并更新线段树。

路径查询

search(u,v) 函数：

• 分解路径为链： 不断将 u 和 v 向上跳转到所在链的顶部，直到到达同一链。

线段树区间查询：

• 对每条链对应的 DFS 序区间进行查询，判断是否存在停机节点。

合并结果：

• 返回路径上是否存在停机节点。

AC 呆麻

#include <bits/stdc++.h>
#define lson (i<<1)
#define rson (i<<1|1)
using namespace std;
const int N=200010;
int n,m,a[N],b[N],d[N],f[N],sz[N],sn[N],tp[N],dfn[N],tim;//各类变量，含义上文已解释
vector<int> p[N];//树存边
struct//线段树结构体
{
    int l,r,v;
}t[4*N];
void build(int i,int l,int r)//建树
{
    t[i].l=l;t[i].r=r;
    t[i].v=0;
    if(l==r) return;
    int mid=(l+r)>>1;//分治
    build(lson,l,mid);
    build(rson,mid+1,r);
}
void update(int i,int x)//更新结点状态
{
    if(t[i].l==t[i].r)
    {
        t[i].v=1;
        return ;
    }
    if(x<=t[lson].r) update(i<<1,x);//二分搜索
    else update(i<<1|1,x);
    t[i].v=max(t[lson].v,t[rson].v);//更新状态
}
int check(int i,int l,int r)//检查路径状态
{
    if(t[i].l>=l and t[i].r <=r)
    {
        return t[i].v;
    }
    int mid=t[i].l+t[i].r>>1,ans;
    if(l<=mid) ans=check(lson,l,r);
    if(r>mid) ans=max(ans,check(rson,l,r));
    return ans;
}
void dfs1(int x,int fa)//dfs1处理深度，父节点，重量
{
    f[x]=fa;d[x]=d[fa]+1;sz[x]=1;
    for(int k:p[x])
    {
        if(k!=fa)//深搜遍历
        {
            dfs1(k,x);
            sz[x]+=sz[k];
            if(sz[k]>sz[sn[x]]) sn[x]=k;
        }
    }
}
void dfs2(int x,int tt)//剖分
{
    tp[x]=tt;dfn[x]=++tim;
    if(!sn[x]) return ;
    dfs2(sn[x],tt);
    for(int k:p[x])
        if(k!=f[x] and k!=sn[x]) dfs2(k,k);
}
int lca(int u,int v){//lca处理结点深度
    while(tp[u]!=tp[v]){
        if(d[tp[u]]<d[tp[v]])swap(u,v);
        u=f[tp[u]];
    }
    return d[u]<d[v]?u:v;
}
int search(int u,int v){//路径上结点的搜索
    int ans=0;
    while(tp[u]!=tp[v]){
        if(d[tp[u]]<d[tp[v]])swap(u,v);//找更深的
        ans=max(ans,check(1,dfn[tp[u]],dfn[u]));
        u=f[tp[u]];
    }
    if(d[u]>d[v])swap(u,v);
    ans=max(ans,check(1,dfn[u],dfn[v]));
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<n;++i){
        cin>>u>>v;
        p[u].push_back(v);p[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    vector<pair<int,int>> ap;
    vector<int> vj(m);
    for(int i=0;i<m;++i){
        cin>>a[i]>>b[i];
        int lc=lca(a[i],b[i]);
        vj[i]=lc; //修改为选择LCA节点
        ap.emplace_back(-d[lc],i); //按LCA的深度排序
    }
    sort(ap.begin(),ap.end());
    vector<int> ans;
    //双层循环遍历
    for(auto& p:ap){
        int i=p.second;
        if(!search(a[i],b[i])){
            ans.push_back(vj[i]);
            update(1,dfn[vj[i]]);
        }
    }
    cout<<ans.size()<<'\n';
    for(int x:ans)cout<<x<<' ';
    return 0;
}

第一次写题解，很可能有不清楚不严谨之处，尽力改正