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

一些题解

G
树上DFS + set启发式合并

题意:

给定一棵树和一个排列p , 给定若干次询问 每次询问给出l,r,x
求是否p[l]~p[r]有一个结点的祖先是x

思路:

不妨做个映射,把每个结点的编号映射为它在排列中的下标
那么转化为求x的子树中是否有l~r结点存在
考虑怎么判断:
对于给定的l,r,x ,若知道x的子树结点的集合,那么只需二分判断是否存在>=l并且<=r的元素存在即可

我们做一个DFS , 每次找出每个结点的重儿子,先将它的set转移而非合并到此节点的set中,其他节点的set暴力合并即可

复杂度O(n(logn)^2)

void solve(){int n,q;cin>>n>>q;vector<pii>edge;rep(i,1,n-1){int u,v;cin>>u>>v;edge.pb({u,v});}vector<int>p(n+1);vector<vector<pair<pii,int>>>qr(n+1);rep(i,1,n){int x;cin>>x;p[x]=i;}rep(i,1,q){int l,r,x;cin>>l>>r>>x;qr[p[x]].pb({{l,r},i});}vector<set<int>>s(n+1);vector<vector<int>>e(n+1);vector<int>ans(q+1,0);for(auto[l,r]:edge){e[p[l]].pb(p[r]);e[p[r]].pb(p[l]);}auto dfs =[&](auto&&self,int u,int fa)->void{int h=u;for(int v:e[u]){if(v==fa)continue;self(self,v,u);if(s[v].size()>s[h].size())h=v;}if(h!=u)swap(s[u],s[h]);s[u].insert(u);for(int v:e[u]){if(v==fa||v==h)continue;s[u].insert(s[v].begin(),s[v].end());}for(auto[PII,idx]:qr[u]){auto[l,r]=PII;auto px = s[u].lower_bound(l);if(px!=s[u].end() && (*px)<=r)ans[idx]=1;}};dfs(dfs,p[1],p[1]);rep(i,1,q){if(ans[i]==1)cout<<"YES"<<endl;else cout<<"NO"<<endl;}
}
http://www.hskmm.com/?act=detail&tid=37675

相关文章:

  • Node.js JSON import attributes All In One
  • DeepSeek的“认知提纯”能力解析
  • 梦熊知更鸟赛水题题解合集 (两个人的演唱会 使一颗心免于哀伤 空气蛹)
  • CF2154D
  • Plya 定理学习笔记 | ABC428G 题解
  • 第十八天
  • 第十七天
  • vue3+elementPlus el-date-picker 自定义禁用状态hook 建立结束时间不能小于开始时间
  • [优先队列] P3611 [USACO17JAN] Cow Dance Show S 题解
  • 搜维尔科技将携手Xsens|Haption|Tesollo|Manus亮相IROS 2025国际智能机器人与系统会议
  • 【做题记录】贪心--提高组
  • 如何炫酷地使用集合划分容斥
  • 简单云计算算法--20251023
  • 处理空输入踩的坑
  • latex输入公式
  • 【为美好CTF献上祝福】 New Star 2025 逆向笔记
  • XXL-JOB(5)
  • 蛋白表达原理与关键要素解析
  • Ramanujan Master Theorem
  • 顾雅南的声音美化课堂
  • C++案例 自定义数组
  • 【周记】2025.10.13~2025.10.19
  • 背包
  • 10.23《程序员修炼之道 从小工到专家》第二章 注重实效的途径 - GENGAR
  • 玩转单片机之智能车小露——LED闪烁实战
  • ord() 函数
  • 2025.10.23总结 - A
  • 大模型 | VLA 初识及在自动驾驶场景中的应用
  • ExPRT.AI如何预测下一个将被利用的漏洞
  • Redis中的分布式锁之SETNX底层实现