当前位置: 首页 > news >正文

P11967 [GESP202503 八级] 割裂

解题思路

问题分析

我们需要找到满足以下条件的节点:

  1. 删除该节点后,所有好点对仍然连通

  2. 删除该节点后,坏点对不连通

关键思路

  1. 好点对连通性分析:

    • 如果一个节点在某个好点对的路径上,删除它会导致该好点对不连通

    • 因此,能被删除的节点不能在任何好点对的路径上

    • 使用树上差分标记所有好点对路径上的节点

  2. 坏点对连通性分析:

    • 删除节点后坏点对要不连通,说明该节点必须在坏点对的路径上

    • 因此,能被删除的节点必须在坏点对的路径上

  3. 综合条件:

    • 节点必须在坏点对路径上

    • 节点不能在任何一个好点对路径上

算法步骤

  1. 构建树并预处理LCA

  2. 使用树上差分标记所有好点对路径上的节点

  3. 遍历坏点对路径,统计满足条件的节点

代码注释

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 10,inf = 0x3f3f3f3f;
vector<int> g[N];  // 邻接表存储树
int n,m;           // n:节点数, m:好点对数量
int s[N];          // 备用数组
vector<pii> a;     // 存储好点对
int vis[N];        // 备用标记数组
int f[N][25],dep[N]; // f:倍增数组, dep:节点深度
int b1,b2;         // 坏点对的两个节点
int ans;           // 答案:满足条件的节点数
int d[N];          // 差分数组,标记好点对路径上的节点// DFS预处理LCA和深度
void dfs(int x,int fa)
{f[x][0] = fa;           // 直接父节点dep[x] = dep[fa] + 1;   // 深度为父节点深度+1// 预处理倍增数组for(int i = 1; i <= 20; i++){int y = f[x][i - 1];f[x][i] = f[y][i - 1];}// 递归处理子节点for(int i = 0; i < g[x].size(); i++){int y = g[x][i];if(y == fa) continue;dfs(y,x);}
}// DFS计算差分数组的前缀和
void dfs2(int x,int fa)
{for(int i = 0; i < g[x].size(); i++){int y = g[x][i];if(y == fa) continue;dfs2(y,x);d[x] += d[y];  // 子节点的值累加到父节点
    }
}// 求两个节点的最近公共祖先(LCA)
int lca(int x,int y)
{// 确保x是深度较大的节点if(dep[x] < dep[y]) swap(x,y);// 将x提升到与y同一深度for(int i = 20; i >= 0; i--){int fa = f[x][i];if(dep[fa] >= dep[y]){x = fa;}} if(x == y) return x;  // 如果相等,y就是LCA// 同时提升x和y直到它们的父节点相同for(int i = 20; i >= 0; i--){int fx = f[x][i],fy = f[y][i];if(fx != fy){x = fx,y = fy;}}return f[x][0];  // 返回LCA
}int main()
{cin >> n >> m;// 读入树结构for(int i = 1; i < n; i++){int x,y; cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}// 预处理LCAdfs(1,0);// 处理所有好点对for(int i = 1; i <= m; i++){int x,y; cin >> x >> y;int rt = lca(x,y);  // 求好点对的LCA// 树上差分标记好点对路径上的节点// 在x和y处+1,在LCA处-1,在LCA的父节点处-1d[x]++,d[y]++,d[rt]--,d[f[rt][0]]--;}// 计算差分数组的前缀和,d[x] > 0 表示节点x在某个好点对的路径上dfs2(1,0);// 读入坏点对cin >> b1 >> b2;int rt = lca(b1,b2);  // 坏点对的LCA// 遍历坏点对路径,统计满足条件的节点// 条件:在坏点对路径上(d[节点] == 0)且不在任何好点对路径上while(b1 != rt){if(d[b1] == 0) ans++;  // 不在好点对路径上b1 = f[b1][0];         // 向LCA移动
    }while(b2 != rt){if(d[b2] == 0) ans++;  // 不在好点对路径上b2 = f[b2][0];         // 向LCA移动
    }if(d[rt] == 0) ans++;      // 检查LCA本身
    cout << ans;return 0;
}

 

http://www.hskmm.com/?act=detail&tid=26876

相关文章:

  • 用 Ada 实现英文数字验证码识别
  • P11380 [GESP202412 八级] 排队
  • 数据增强操作
  • HTML5实现简洁的端午节节日网站源码 - 实践
  • Visio的图片,粘到word中显示不全,右边和下面显示不出来
  • 25国庆总结
  • 某平台增强排序脚本
  • 印度乡村AI计划:用JAN AI打造人工智能优先村庄
  • # Java方法学习:动手动脑与课后实验整理
  • CF2155D Batteries
  • JAVA语法基础》动手动脑与实验问题全整理
  • 崩铁壁纸
  • PotPlayer 播放器
  • 10.8动手动孬
  • [迷宫寻路 Round 3] 七连击
  • 《程序员修炼之道:从小工到专家》阅读笔记
  • [笔记]树论笔记+做题记录
  • 云服务器部署大数据组件
  • 规模化网站SSL证书终极方案
  • 详细介绍:录制mp4
  • 10月8日
  • 【OpenGL ES】光栅化插值原理和射线拾取原理
  • HTML 速查列表 - 教程
  • Exp1
  • 20_uv_wsl_installation
  • 学习问题日记-4
  • Codeforces Round 1042 (CF2131) 补题笔记(A-E)
  • 在AI技术唾手可得的时代,挖掘新需求成为核心竞争力——某知名AI编程助手框架需求探索
  • 表格数据自动机器学习技术解析
  • 10/8